Necessary and sufficient condition so that L be equal to L*

58 Views Asked by At

Given L a formal language, what are the necessary and sufficient conditions so that L = L*
Definition of L* is: $$ L^*=\bigcup_{i\in \mathbb{N}_0}L^i=L^0\cup L^1\cup L^2\dots $$

1

There are 1 best solutions below

1
On

A condition, what is neccessary and sufficient is $\{\lambda\} \cup L^2 \subseteq L$, where $\lambda$ denotes the empty word.

For the proof, note that on one side, $\{\lambda\} \cup L^2 = L^0\cup L^2 \subseteq L^*$ by definition. On the other side, we will prove by induction that $L^i \subseteq L$. For $i = 0$, $L^0 = \{\lambda\} \subseteq L$ by our condition. Now suppose, for some $i$, we have $L^i \subseteq L$. We now have $$ L^{i+1} = LL^i \subseteq L L = L^2 \subseteq L,$$ the last inclusion by our condition.