4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.