Thread: regular expressions help

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    regular expressions help

    Well I’m studying for my Languages and Automata class and I do not understand a few examples regarding certain regular expressions:

    In each example assume that the alphabet ∑ is {0,1}

    1. ( ∑∑ )* = {w|w is a string of even length}
    I don’t follow this…I can rewrite this to: ({0,1}{0,1})*, and this would imply that the language consists of all possible pairs of 0s and 1s.

    2. ( ∑∑∑ )* = {w|the length of w is a multiple of three}
    This one is similar to the one above, I simply don’t get it.

    3. (0∑*0) U (1∑*1) U (0) U (1) = {w|w starts and ends with the same symbol}
    I tried dissecting this one, but I still don’t understand: (0∑*0) means all strings that begin and end with 0; (1∑*1) – all strings that begin and end with 1; so how does the rest of the expression ‘U (0) U (1)’ make the first and last symbol the same?


    Any help will be appreciated. Man, this will be one “fun” class….
    Last edited by axon; 09-09-2004 at 02:19 PM.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    I read my own post...and now I get the first two examples. The whole bit about "all possible pairs of 0s and 1s." makes the string even...duh (see, its always good to write your own thoughts down, they start making sense - sometimes). And number two is the same thing, but instead of a pair we have a triple.

    But the third example is still confusing...

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    someone has explained the examples to me via reputation, but did not leave a name, so I don't know whom to thank...I'm not sure who it was, but am leaning towards webmaster.

    well, whoever it was, thank you very much!

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    ...and for those of us who are still curious about number 3.... how bout a quick explanation of how that can end in 0 or start in 1.

    i havent taken any Language and Automata courses yet, seems interesting though.

  5. #5
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    well the unions with the sets {0} and {1} are made in case the string consists of only one 1 or one 0 - in that case it starts, and ends, with the same character

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Regular expressions [Boost]
    By Desolation in forum C++ Programming
    Replies: 8
    Last Post: 12-30-2006, 10:10 PM
  2. Regular expressions
    By JimpsEd in forum C Programming
    Replies: 5
    Last Post: 05-13-2006, 06:01 PM
  3. Help please: regular expressions in C++
    By reivaj7999 in forum C++ Programming
    Replies: 3
    Last Post: 08-24-2005, 01:11 AM
  4. Regular expressions
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 01-23-2005, 09:36 PM
  5. Regular Expressions
    By Korn1699 in forum C# Programming
    Replies: 4
    Last Post: 01-12-2005, 12:50 AM