Regular Language Equivalence Question

Hi guys

I'm working through the recommended examples, and have run into something strange.

Problem 12 i for chapter four asks you to say why two expressions are equivalent.

Now, the answer they give in the study guide doesn't quite make sense. As far as I can tell, you can construct the word "abbba" with the first expression, but not he second. Surely that means they aren't equivalent? As far as I understand it, if they are equivalent, they refer to the same language, meaning they have all the same words.

Am I missing something?

Hi Justice

you can construct the word 'abbba' with the second regular expression that is (a + b)*ab(a + b)* I will try to explain:

So from the first (a+b)* we take the empty set ? so we have ab( a + b)* left.
We must allow ab and with (a + b)* build up the rest of your word that is bba.
That is easy because we have a closure over a or b eg. (a + b)*.
So we build the word in the following steps:

ab (this must be in every word)
abb (we selected a b from our closure)
abbb (we selected another b from our closure)
abbba (we selected a a from our closure)

and thus we created the word 'abbba' from the regular expression.

Remember if our alphabet is only the set {a, b} you can build any word with the regex (a + b)*. So read the answer in the study guide again you will see they point out the word will contain any amount of a b(or ?) in the beginning and then followed by ab and then contain any amount of a b (or ? again) in the end.

Hope this helps,

PS. I tried to reply yesterday but the phorum crashed the whole time! I only realize now after I tried to find the problem is that the forum does not like utf-8 characters so all the ? in my answer above is actually the uppercase Lambda sign.

Ahh, I see now. Thanks.

I was being stupid with the closure. I didn't click that you can do the last (a+b)* bit as often as you want to get the required expression. For some reason I thought you could only pass through it once.

Appreciate the help!