0

Let $L$ be the language generated by the regular expression $(b \cup ab \cup aab)^*(\lambda \cup a \cup aa)$. how does bbbbbbabaabaa belong to L?

I know $(b \cup ab \cup aab)^*$ can be translated to $bbbbbb$

and $(\lambda \cup a \cup aa)$ can be translated to $aa$

then where does abaab come from? is it from $(b \cup ab \cup aab)^*$? if so, i thought $\cup$ was a "either or" statement, not a "both or all" statement.

so $(b \cup ab \cup aab)$ can be:

$b$ or $ab$ or $aab$. but not $babaab$ or definitely $bbbbbbabaab$.

I'm assuming i'm not fully understanding a minor concept.

Thank you.

martini
  • 84,101
user1486802
  • 743
  • 1
    Like this: $(b)(b)(b)(b)(b)(b)(ab)(aab)(aa)$. In $L = (b \cup ab \cup aab)^* (\lambda \cup a \cup aa)$ the connective $\cup$ (in other notations $|$ symbol) behaves much like a set union, i.e. $(a \cup b)^2$ would denote ${aa,ab,ba,bb}$ in analogy to $({a} \cup {b})^2$. – dtldarek Oct 18 '13 at 07:28
  • @dtldarek, thanks alot! crystal clear! – user1486802 Oct 18 '13 at 07:35

1 Answers1

1

$L$ is generated by the regular expression $(b\cup ab\cup aab)^*(\lambda\cup a\cup aa)$. If $bbbbbbabaabaa\in L$, clearly we must match the final $aa$ with the $aa$ alternative of $\lambda\cup a\cup aa$, so the initial segement $bbbbbbabaab$ must match $(b\cup ab\cup aab)^*$. And it does:

$$bbbbbbabaab=(b)(b)(b)(b)(b)(b)(ab)(aab)\;,\tag{1}$$

where each expression in parentheses matches one of the alternatives of $b\cup ab\cup aab$. Since the star of this permits us to concatenate any finite number of instance of any of these three alternatives, $(1)$ is generated by $(b\cup ab\cup aab)^*$, and $bbbbbbabaabaa$ is generated by the original regular expression.

Brian M. Scott
  • 616,228