Arden's lemma applicability on context free grammars

Question

The Arden's lemma states that there exists a solution to the equation between regular expressions r = 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 like

S->AS|b

so 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|A

A->aAa|Ab|e

and 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?

Answer 1

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)^*$.