We have languages $A= \{a\}$ and $B = \{b\}$. If we consider $(A\cup B)^*$, where ${}^*$ means Kleene star, we have a set of words like $\{\lambda, a,b,aa,ab,aaa,\dots\}$, where $\lambda$ is the empty word. Another example we do is $A^*(BA^*)^*$. If we concatenate two languages, $\lambda$ will not be in the set, but the Kleene star adds the $\lambda$. Question is, is this set same as the set with union so $\{\lambda,a,b,aa,ab,aaa,\dots\}$ or is the set for the second example $\{a,b,aa,ab,aaa,\dots\}$, in which case the langauages would not be equal. My opinion is that concatenation is the last operation so sets are not equal but I'm not sure.

  • 1
    $\begingroup$ "If we concatenate two languages, $\lambda$ will not be in the set" - This is not quite right. The concatenation $L_1 L_2$ does include $\lambda$, if $\lambda \in L_1$ and $\lambda \in L_2$. $\endgroup$ – D.W. Oct 6 '15 at 23:53
  • $\begingroup$ "is this set same as the set" - Which set? I'm confused by your pronouns. I suggest you give the sets names (e.g., $C$, $D$, etc.) so you can refer to them clearly. $\endgroup$ – D.W. Oct 6 '15 at 23:54

Unless parentheses say otherwise, the customary precedence is ${}^*$ (like exponentiation), then concatenation (like multiplication), then union (like addition).

Your second example is the concatenation of starred expressions, so it does contain the empty string.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.