patternMinor
Arden's lemma applicability on context free grammars
Viewed 0 times
freeardengrammarslemmacontextapplicability
Problem
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?
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?
Solution
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)^$.
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)^$.
Context
StackExchange Computer Science Q#45655, answer score: 3
Revisions (0)
No revisions yet.