PDA

View Full Version : regular expressions help



axon
09-09-2004, 02:12 PM
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….:(

axon
09-09-2004, 02:19 PM
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 :o (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... :(

axon
09-09-2004, 07:06 PM
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! :)

Perspective
09-09-2004, 07:12 PM
...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.

axon
09-09-2004, 07:16 PM
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 :)