The question is: For all languages $L_1$ and $L_2$ , if $L_1^* = L_2^*$, then $L_1 = L_2$.

We know that two languages are equivalent if $L(G_1) = L(G_2)$, where $L(G) = \{w \in T^* \mid S\Rightarrow^*w\}$. Two grammars are equivalent if the quadruple of $G_1 = (\Sigma_1,N_1,P_1,\sigma_1)$ and $G_2 = (\Sigma_2,N_2,P_2,\sigma_2)$ generate the same formal languages.

I think this statement is true, because they have to accept the same formal languages regardless if its called multiple times.

I'm asking this question so someone can confirm it, knows an exception, or has a proof.

  • $\begingroup$ Hint: Check $L=\{a,b\}$. $\endgroup$ – Ran G. Apr 1 at 13:10
  • 1
    $\begingroup$ Another hint: $L^{**} = L^*$. $\endgroup$ – Yuval Filmus Apr 1 at 13:46

Certainly not. Consider $L_1=\{a\}$ and $L_2=\{\epsilon, a\}$.

| cite | improve this answer | |

Your Answer

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