Question about equlaity of two language, simple but tricky.

69 Views Asked by At

I found the following question tricky:

If $A$ is a language, when will $A^*=A^+$?

By definition,

$$A^* = \bigcup^{\infty}_{i=0}A^i = A^0 \cup A^1 \cup A^2 \cup \cdots$$

$$A^+ = \bigcup^{\infty}_{i=1}A^i =A^1 \cup A^2 \cup \cdots$$

Also, $A^0=\{\epsilon\}$

So, $A^* = A^+$ if and only if $\{\epsilon\} \cup A^+=A^+$. I feel like this can be simplified further.

For example, I can claim that if $A=\{\epsilon \} $, then $A^*=A^+$.But I am not sure. Thanks for your help!

1

There are 1 best solutions below

3
On BEST ANSWER

Suppose that $A^*=A^+$. By definition, $\varepsilon$ is in $A^*$, so it's in $A^+$. Therefore $\varepsilon$ is in $A$ or $A^2$ or. . . But this just means that $\varepsilon\in A$. The converse is easy to prove, so $$A^*=A^+\quad\hbox{if and only if}\quad \varepsilon\in A\ .$$