Converting to unambiguous grammar from ambiguous grammar

Question

I've ambiguous context-free grammar which has products:

s --> [0],s,[1].
s --> [0],s.
s --> [].

It's of course ambiguous because for 00011 I can draw two others parsing trees. I have to write my grammar which is unambiguous grammar and describes the same language. My idea is:

   s --> [0],s,[1].
   s --> [0],a.
   s --> [].
   a --> [0],a.
   a --> [].

It's good? And how I can prove it?

0 and 1 is our alphabet. [] mean empty set and , is use on Prolog. We write S -> 0S1 when on prolog it's s --> [0],s,[1]. — Vous
though there is no algorithm solution to verify whether the grammar is ambiguous or not (and two grammars are equivalent) So only trick you have is aptitude, proof by analysis. — Grijesh Chauhan
You have to argue that for each string in the language there is only one derivation tree using your second grammar. ---It become very long answer If I teach you how to approach these kind of questions (That can be possible you can wait?) -- Do you understand operator precedence? or flow of generation? — Grijesh Chauhan
To justify your answer: tell your teacher: "In my second version grammar you have first generate all 1's then, once you more to s --> [0],a. production you can't add 1 in string. (and if you think 0 nas 1 as operator then precedence of 0 is higher over 1 as it get possition lower in parse tree )" You can read this answer to know precedence idea — Grijesh Chauhan

false false · Accepted Answer · 2014-06-17T11:18:43

So how can you prove ambiguity? In Prolog, this is easily possible for concrete sentences:

| ?- length(Xs,N), bagof(t,phrase(s,Xs),[_,_|_]).              

N = 3
Xs = [0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 5
Xs = [0,0,0,0,1] ? ;

N = 5
Xs = [0,0,0,1,1] ? ;

N = 6
Xs = [0,0,0,0,0,1] ?

This proves that there is ambiguity for concrete length and gives the relevant counterexample.

There is, however a caveat which might show only after some time: bagof/3 has to store the entire set of solutions somehow. So if this set is very large, bagof/3 might overflow. The following query avoids this bug at the price of getting redundant solutions:

| ?- length(Xs,N), phrase(s,Xs), bagof(t,phrase(s,Xs),[_,_|_]).

N = 3
Xs = [0,0,1] ? ;

N = 3
Xs = [0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 5
Xs = [0,0,0,1,1] ...

with your improved grammar, the query loops. That means that the system cannot find a counterexample. At least not with a length below 1000 which is what I tested.

Some general remarks about writing DCGs in Prolog:

Try to put the recursive case last, this might save some space.
You might want to use double-quoted strings to represent terminals. See this answer for more.

Converting to unambiguous grammar from ambiguous grammar

1 Answers