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….:(

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….:(