3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You have pretty much the right idea, but you are missing one fact: you can use some of the well known closure properties of CF languages. When you prove them the hard way by actual construction, you see they they are often structure preserving, which is very useful when you want to preserve parse-trees, or just ambiguity. So much for the myth that formal grammars define only sets of strings. So, as you suggest, you just remove your ambiguous strings (by intersection), and add them separately. $\endgroup$ – babou Nov 23 '14 at 13:35
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You say that "This grammar $G'$ is not ambiguous, since it has exactly the same parse trees as $G$, up to renaming of non-terminals." How do we know this is true? Since $G'$ has all the same leftmost derivations as the leftmost derivations in $G$ for all the unambiguous strings in $G$, this suggests to me that $G'$ keeps some (or all) the rules of $G$. But then isn't there a possibility that these rules could be used by $G'$ to generate the ambiguous strings in the old grammar? $\endgroup$ – CS_Student395 Nov 23 '14 at 18:29
  • $\begingroup$ @CS_Student395 The crossproduct construction is such that any derivation of $G'$ mimics a derivation of $G$, and conversely, except for strings of the CF language that are not in the regular language. These strings are not accepted because the mimicking of the FSA $\bar R$ sees to that. Not that actually you should use a DFA to make sure there is only one accepting computation of the $\bar R$ for each string. I will add this to the answer (I am working of some other additions, with no direct bearing on the proof, and I will do all at the same time) $\endgroup$ – babou Nov 23 '14 at 20:20
  • $\begingroup$ I'm a bit confused when you say to apply the cross-product construction to $G$ and $\overline{R}$. Do you mean to say to take the cross-product construction of the PDA simulating $G$ and the DFA $\overline{R}$? If so, you seem to be suggesting that the resulting PDA, obtained from this cross-product construction, simulates a grammar that has "exactly the same parse trees as $G$". Is this correct? $\endgroup$ – David Smith Nov 24 '14 at 9:52
  • $\begingroup$ @DavidSmith A FSA can always be viewed as a gammar, where the states are non-terminals and the transitions are rules, if you feel more comfortable with two grammars. For good reasons, I like to see the construction as based on the CFG where derivations are being checked by the FSA. Then the non terminals of $G'$ are triples $(p,A,q)$ where $p,q$ are DFA states and $A$ is a non-terminal of $G$. Then you have $G'$ rules that look like $(p,A,q)\to(p,B,r)(r,C,q)$ when $A\to BC$ is a rule in $G$, and $(p,A,q)\to a$ when $A\to a$ is in $G$ and $(p,a)\mapsto q$ is a transition in the DFA. $\endgroup$ – babou Nov 24 '14 at 10:13
  • $\begingroup$ @CS_Student395 I may do some editing to improve the presentation of the answer, and include some points from my comments, including the details of the cross-product construction. Are there other issues that are bothering you regarding that answer? $\endgroup$ – babou Nov 24 '14 at 23:27

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.