Let L be the language defined by the regular expression:
(a U b U c)((ab U ac U b)*(a U b) U (aa)*)
the answer book says that 'aaaa' and 'aaaaaa' do not belong to L. I can show that aaaa and aaaaaa is deducable using the reg exp per above:
aaaa:
a U b U c -> a
ab U ac U b -> empty string
a U b -> a
(aa)* -> aa
so aaaa
for aaaaaa:
a U b U c -> a
ab U ac U b -> empty string
a U b -> a
(aa)* -> aaaa
so, aaaaaa
Am i doing something wrong here? thank you.
The regular expression is a concatenation of $a\cup b\cup c$ and $(ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*$, so after you take $a$ from $a\cup b\cup c$, you must choose either from $(ab\cup ac\cup b)^*$ or from $(aa)^*$; you can’t use both, because they’re alternatives within the expression $$(ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*\;.$$ (In my original comment, now deleted, I missed the parentheses around $$(ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*\;,$$ reading the expression as $(a\cup b\cup c)(ab\cup ac\cup b)^*(a\cup b)\cup(aa)^*$, a union (or disjunction) of two expressions rather than as a concatenation.)
If you choose from $(ab\cup ac\cup b)^*$, you clearly won’t get all $a$’s, so you must choose from $(aa)^*$. That gives you $2n$ $a$’s for some $n\ge 0$, so together with the initial $a$ from $a\cup b\cup c$ you have $a^{2n+1}$. In other words, if you generate a string of $a$’s, it necessarily contains an odd number of $a$’s.
You can also see this by ‘multiplying out’ the original regular expression. You get a union (or disjunction) of the following terms:
$$\begin{align*} &a(ab\cup ac\cup b)^*a\\ &a(ab\cup ac\cup b)^*b\\ &b(ab\cup ac\cup b)^*a\\ &b(ab\cup ac\cup b)^*b\\ &c(ab\cup ac\cup b)^*a\\ &c(ab\cup ac\cup b)^*b\\ &a(aa)^*\\ &b(aa)^*\\ &c(aa)^* \end{align*}$$
The only one of these that generates all $a$’s is $a(aa)^*$, which always generates an odd number of $a$’s.