Cheap and Secure Web Hosting Provider : See Now

[Solved]: Kleene star differences

, , No Comments
Problem Detail: 

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.

Asked By : POC

Answered By : vonbrand

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47945

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback