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, Apr 07 '14 at 19:16
Do you understand what is language of your grammar? If you need short answer then yes, you have resolved ambiguity and second form is unambiguous grammar. — Grijesh Chauhan, Apr 07 '14 at 19:29
It's words under alphabet {1,0} which can be produced by this rules: S->0 S 1 ... ? — Vous, Apr 07 '14 at 19:33
No, `S -> 0 S 1` generates 0^n1^n, but your grammar generates [0^n1^m where n >= m](http://stackoverflow.com/a/15130451/1673391) — Grijesh Chauhan, Apr 07 '14 at 19:35
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, Apr 07 '14 at 19:38
Yes so when I use second code from my post /\ I get 0^n1^m where n>-m :) But teacher can ask me "are you sure it's unambiguous grammar?". You know, it's easy to find contradiction but harder to prove the truth. — Vous, Apr 07 '14 at 19:40
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, Apr 07 '14 at 19:47
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](http://stackoverflow.com/a/17170820/1673391) to know precedence idea — Grijesh Chauhan, Apr 07 '14 at 19:51

false · Answer 1 · 2022-08-19T17:42:25.403

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

?- length(Xs,N), bagof(t,phrase(s,Xs),[_,_|_]).   
   Xs = [0,0,1], N = 3
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,0,0,1], N = 6
;  Xs = [0,0,0,0,1,1], N = 6
;  Xs = [0,0,0,0,0,0,1], N = 7
;  ... .

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),[_,_|_]).
   Xs = [0,0,1], N = 3
;  Xs = [0,0,1], N = 3
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,0,1,1], N = 6
;  ... .

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 Answers1