Theory of Computation - Regular expression explanation

[Conrad11]

Just doing some revision and came across these. Is anyone able to give me a quick explanation of 5, 6 & 7?



From how I understand it, the alphabet includes the empty string when the star operation is put on it.

My thoughts on 5 and 6: If the alphabet (E) input is the same for instance (is it <- this bit was the bit that confused me) then its simple because there are 2 and 3 of them so the result must be multiples, but thats only if they are the same. For 5 could you have the resultant string as "010" or would it have to be "0101" (the same)

8 - can't really see why w MUST have a 0 on the start and finish because it could be either with union?

Thanks.

EDIT: I meant 8 NOT 7

 

[Conrad11]

Sigma in the regular expressions is used as a single element from the alphabet.

That's the kicker. If I'd have known that I may have understood.

(SigmaSigma)* will match infinitely many of { 00, 01, 10, 11 } stringed together, hence the overall length will be a multiple of 2.

I take it that the empty string is considered 1 length because the star operation includes the empty string in its resultant set doesn't it?

EDIT: Bugger, I meant number 8 (not 7)!

 

[Conrad11]

The empty string has length 0, it's still even, and a multiple of 3.

Well surely you could get a resultant string from (SigmaSigmaSigma)* as "e00"; which has a length of 2 and not a multiple of three (according to your explanation)....or does the star operation only count after you have read/evaluated (SigmaSigmaSigma) so the resultant set would be { e, 000, 001, 010, 100, 011, ... }.

(0 or e)1* = 01* or 1* because it's distributive. 1* = e1*.

Thats number 9 ....I'm looking for 8

Thank you very much for your responses.

 

[Conrad11]

Bumpty Bump!

 

[Conrad11]

Maybe...can anyone confirm?

 

[Conrad11]

Bumpty!

 

[Conrad11]

Q8:
Sigma* is just any number of 0s or 1s which i will call X for simplicity.

Then the expression reads 0X0 or 1X1 or 0 or 1

The first term, 0X0, it is clear that if the string starts with 0 it must end with a 0. This is the same for 1s too.

However the string "0" begins with a 0 and ends with a 0 but isn't included in the alphabet defined by 0X0 which is why you have to include the "or 0 or 1" as well

Thank you for your answer. But I simply don't understand the last statement (probably a fundamental math problem of mine)

Would putting brackets in it help?

 

[Conrad11]

Multipost

 

[Conrad11]

I am a bit of an pleb. My basic understanding of the union statement was flawed (last post helped rectify that). Weird how simply writing things on new lines helped :/

Thanks.