Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

My problem is how can I prove that a grammar is unambiguous? I have the following grammar: $$S → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S \mbox{ else } S$$

and make this to an unambiguous grammar, I think its correct:

  • $ S → S_1 ∣ S_2 $

  • $S_1 → \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_1$

  • $S_2 → \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_2 ∣ statement$

I know that a unambiguous grammar has one parse tree for every term.

share|improve this question
add comment

3 Answers

There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps:

  1. Prove $L \subseteq \mathcal{L}(G)$.
  2. Prove $[z^n]S_G(z) = |L_n|$.

The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness.

The second step shows that $G$ has as many syntax trees for words of length $n$ as $L$ has words of length $n$ -- with 1. this implies unambiguity. It uses the structure function of $G$ which goes back to Chomsky and Schützenberger [1], namely

$\qquad \displaystyle S_G(z) = \sum_{n=0}^\infty t_nz^n$

with $t_n = [z^n]S_G(z)$ the number of syntax trees $G$ has for words of length $n$. Of course you need to have $|L_n|$ for this to work.

The nice thing is that $S_G$ is (usually) easy to obtain for context-free languages, although finding a closed form for $t_n$ can be difficult. Transform $G$ into an equation system of functions with one variable per nonterminal:

$\qquad \displaystyle \left[ A(z) = \sum\limits_{(A, a_0 \dots a_k) \in \delta} \ \prod\limits_{i=0}^{k} \ \tau(a_i)\ : A \in N \right] \text{ with } \tau(a) = \begin{cases} a(z) &, a \in N \\ z &, a \in T \\ \end{cases}.$

This may look daunting but is really only a syntactical transformation as will become clear in the example. The idea is that generated terminal symbols are counted in the exponent of $z$ and because the system has the same form as $G$, $z^n$ occurs as often in the sum as $n$ terminals can be generated by $G$. Check Kuich [2] for details.

Solving this equation system (computer algebra!) yields $S(z) = S_G(z)$; now you "only" have to pull the coefficient (in closed, general form). The TCS Cheat Sheet and computer algebra can often do so.


Example

Consider the simple grammar $G$ with rules

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$.

It is clear that $\mathcal{L}(G) = \{ww^R \mid w \in \{a,b\}^*\}$ (step 1, proof by induction). There are $2^{\frac{n}{2}}$ palindromes of length $n$ if $n$ is even, $0$ otherwise.

Setting up the equation system yields

$\qquad \displaystyle S(z) = 2z^2S(z) + 1$

whose solution is

$\qquad \displaystyle S_G(z) = \frac{1}{1-2z^2}$.

The coefficients of $S_G$ coincide with the numbers of palindromes, so $G$ is unambiguous.


  1. The Algebraic Theory of Context-Free Languages by Chomsky, Schützenberger (1963)
  2. On the entropy of context-free languages by Kuich (1970)
share|improve this answer
    
As you know @Raphael, ambiguity is not decidable, so at least one of your steps cannot be mechanised. Any idea which ones? Getting a closed form for $t_n$? –  Martin Berger Feb 10 '13 at 7:32
    
The equation system may not be solvable algorithmically if the degree is too high, and pulling the exact coefficients out of the generating functions can be (too) hard. In "practice", though, one often deals with grammars of small "degree" -- note that, say, Chomsky normal form leads to equation systems of small degree -- and there are methods to get at least $\sim$-asymptotics for the coefficients; this may be sufficient to establish ambiguity. Note that in order to prove unambiguity, showing $S_L(z) = S_G(z)$ without pulling coefficients is enough; proving this identity may be hard, though. –  Raphael Feb 10 '13 at 13:59
    
Thank you @Raphael. Do you know of any texts that develop in detail how undecidability comes into play even if one uses e.g. Chomsky normal form? (I can't get hold of Kuich.) –  Martin Berger Feb 11 '13 at 10:32
    
@MartinBerger I just rediscovered your comment in my todo list; sorry for the long silence. There are three steps which (I think) are not computable in general: 1) Determine $S_G$. 2) Compute $|L_n|$. 3) Determine $[z^n]S_g(z)$. In particular, what representation of $L$ to use for 2)? –  Raphael Jan 30 at 11:24
    
Why is representation of $L$ a problem? We can use any of the multiple ways of representing CFGs for compilers for example. Maybe you mean how to represent $L_n$? –  Martin Berger Jan 30 at 16:00
show 1 more comment

Basically, it's a child generation problem. Start with the first expression, and generate it's children .... Keep doing it recursively (DFS), and after quite a few iterations, see if you can generate the same expanded expression from two different children. If you are able to do that, it's ambiguous. There is no way to determine the running time of this algorithm though. Assume it's safe, after maybe generating 30 levels of children :) (Of course it could bomb on the 31st)

share|improve this answer
    
The OP asks for proof techniques, not algorithms. –  Raphael Jun 11 '12 at 10:46
add comment

This is a good question, but some Googling would have told you that there is no general method for deciding ambiguity, so you need to make your question more specific.

share|improve this answer
    
The OP asks for proof techniques, not algorithms. –  Raphael Jun 11 '12 at 10:46
    
I think so, too; it might be mentioned in the question. –  reinierpost Jun 11 '12 at 15:37
    
Google is not an oracle of truth, because knowlede is not democratic, and Google results are. I wouldn't count on Google in this case, because people often copy-cat one from another without checking the correctness of what they copy. Without showing a proof, they might be wrong. –  SasQ Aug 6 '12 at 15:18
    
@SasQ: You read my words too literally. What Google gives me is the URLs to aticles that explain things. –  reinierpost Oct 5 '12 at 11:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.