snippetMinor
How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?
Viewed 0 times
newconvertwithintofinitelyunambiguousambiguousgrammarmanyhow
Problem
Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If so, how would I go about doing this? One starting approach I see is to have rules of the form $S \longrightarrow w $ in the new grammar, where $w$ is a string that was ambiguous in the original grammar. I'm not sure; however, how I'd go about modifying the original grammar to a further extent. Of course, we'd like to keep much of $G$ for our new grammar, insofar as $G$ unambiguously generates strings of sufficient length.
Solution
Here is the skeleton of the proof. I leave it to you to fill in the
details.
Let $R$ be a FSA recognizing the set $A$ of ambiguous strings of $G$
(yes, I am generalizing a bit the problem to regular sets of ambiguous words, since it is no harder). Let
$\bar R$ be a DFA recognizing the complement $\bar A$ of $A$: $\bar
A=\Sigma^*-A$.
We can use the cross-product construction for intersection of the
languages of a CF-grammar and a FSA, applying it to $G$ and $\bar R$
to get a CF grammar $G'$ that recognnizes $L'=L-A$. This grammar $G'$ is
not ambiguous, since it has exactly the same parse trees as $G$, up to
renaming of non-terminals (and the ambiguous words have been removed).
The FSA $\bar R$ has been chosen deterministic to make sure it has at most one accepting computation on any input, and thus does not introduce new ambiguities.
Then, Since the language $A$ is regular, it is easy to produce a
non-ambiguous CF (or regular) grammar $F$ that recognizes $A$.
Then, given the two non-ambiguous grammars $G'$ and $F$, generating
respectively $L'=L-A$ and $A$ which have an empty intersection, it is
easy, with one extra production rule, to produce a non-ambiguous grammar $G''$ that
recognizes the union $L'\cup A=(L-A)\cup A=L$.
So the non-ambiguous grammar $G''$ generates the language $L$. QED
That is all very nice, but given some CF grammar G you may not be able
to do all this, even when it is actually possible.
details.
Let $R$ be a FSA recognizing the set $A$ of ambiguous strings of $G$
(yes, I am generalizing a bit the problem to regular sets of ambiguous words, since it is no harder). Let
$\bar R$ be a DFA recognizing the complement $\bar A$ of $A$: $\bar
A=\Sigma^*-A$.
We can use the cross-product construction for intersection of the
languages of a CF-grammar and a FSA, applying it to $G$ and $\bar R$
to get a CF grammar $G'$ that recognnizes $L'=L-A$. This grammar $G'$ is
not ambiguous, since it has exactly the same parse trees as $G$, up to
renaming of non-terminals (and the ambiguous words have been removed).
The FSA $\bar R$ has been chosen deterministic to make sure it has at most one accepting computation on any input, and thus does not introduce new ambiguities.
Then, Since the language $A$ is regular, it is easy to produce a
non-ambiguous CF (or regular) grammar $F$ that recognizes $A$.
Then, given the two non-ambiguous grammars $G'$ and $F$, generating
respectively $L'=L-A$ and $A$ which have an empty intersection, it is
easy, with one extra production rule, to produce a non-ambiguous grammar $G''$ that
recognizes the union $L'\cup A=(L-A)\cup A=L$.
So the non-ambiguous grammar $G''$ generates the language $L$. QED
That is all very nice, but given some CF grammar G you may not be able
to do all this, even when it is actually possible.
Context
StackExchange Computer Science Q#33419, answer score: 3
Revisions (0)
No revisions yet.