Theory of Computation - Regular expression explanation

Conrad11 · 23 Feb 2010 at 14:11

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

Josh P · 23 Feb 2010 at 15:29

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

Therefore, (SigmaSigma) will match any of { 00, 01, 10, 11 }.

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

The same principle applies for (SigmaSigmaSigma), it will match { 000, 001, 010, 011, 100, 101, 110, 111 }. (SigmaSigmaSigma)* will match a string of these, given that one has length 3 the total will have a length 3n.

(01|10): Because of the way the union operator binds, this is equivalent to ((01)|(10)), hence a matching trace must be drawn from { 01, 10 }.

Hope this helps!

Conrad11 · 23 Feb 2010 at 15:36

Josh P said:
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)!

Josh P · 23 Feb 2010 at 16:01

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

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

Conrad11 · 23 Feb 2010 at 16:08

Josh P said:
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 · 23 Feb 2010 at 18:54

Bumpty Bump!

Pleh · 23 Feb 2010 at 18:57

Hmm, is the answer - Fish?

Conrad11 · 23 Feb 2010 at 18:58

Maybe...can anyone confirm?

Conrad11 · 24 Feb 2010 at 15:29

Bumpty!

marc_howarth · 24 Feb 2010 at 15:43

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

Conrad11 · 24 Feb 2010 at 17:02

marc_howarth said:
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 · 24 Feb 2010 at 17:03

Multipost

Pudney · 24 Feb 2010 at 17:38

Conrad11 said:
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?

Language of Number 8.

0string0

OR

1string1

OR

0

OR

1

string being any amount of language elements.

Conrad11 · 24 Feb 2010 at 18:15

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.