The Arden's lemma states that there exists a solution to the equation between regular expressionsr = sr + t, with r unknown, and it is s*t.I went through some other topics on the forum and I always saw it being applied, for example, on grammars that have productions likeS->AS|bso that L(S) = L(A)L(S) + b and the solution is L(A)*b.However, on some student notes from a classmate I found this example:S->ASA|AA->aAa|Ab|eand the Arden's rule is applied in this way without any further manipulation of the grammar:L(S) = L(A)L(S)L(A) + L(A) and it concludes by saying that L(S) = L(A)*This seems wrong to me, but I want to check first whether there is some further hypothesis that can be applied here to make the statement valid.For example, I wonder if it is decidable (and of course valid) whether the productions S->ASA|A generate the same language of the productions S->AAS|A.Can somebody please help me?
Arden's lemma applicability on context free grammars
formal languages;context free;formal grammars;regular expressions
First of all, let me mention that Arden's lemma applies not only to regular expressions but to any equation among languages of the form $r = sr+t$, where $r,s,t$ are arbitrary languages. The smallest solution to this equation (also known as the least fixed point) is always $r = s^*t$. If $\epsilon \notin s$, then this is in fact the only solution. (Otherwise, $\Sigma^*$ is also a solution.)The language generated by the rule $S\to aSa|a$ is not $a^*$ but rather $a(aa)^*$: only odd powers are allowed. So it seems that the student notes contain a mistake, though in this particular case the calculation yields the correct conclusion since $\epsilon \in L(A)$.On the other hand, $S\to aSa|a$ and $S\to aaS|a$ do generate the same language.More generally, if the only rules involving $S$ are $S \to ASA|A$, then replacing these rules by $S \to AAS|A$ or $S \to A|SAA$ result in the same language, $L(A)(L(A)^2)^*$; and if $\epsilon \in L(A)$, we can further simplify this to $L(S) = L(A)^*$.