HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#33419, answer score: 3

Revisions (0)

No revisions yet.