This question already has an answer here:

I have to find an unambiguous context-free grammar that generates the following language. $$L= \{ w \in \{a,b\}^+ : |w|_a = |w|_b\}$$ I think I have found the context-free one, it should be this one. $$S \to aS'bS'|bS'aS'$$ $$S' \to aS'bS' | bS'aS' | \lambda$$ Now I am stuck with proving whether it is unambiguous or not. I think it is but how should I do that?


marked as duplicate by Community Apr 17 '18 at 18:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Why do you think your grammar is unambiguous? $\endgroup$ – Yuval Filmus Apr 17 '18 at 17:54

Consider the word $abab$. It has two derivation trees (rendered using syntree):

First tree

Second tree

Hence your grammar is ambiguous. In order to make an unambiguous grammar, we have to force the parse to be unique. We identify the word with a path in which $a$ corresponds to $\nearrow$ and $b$ to $\searrow$. We're looking for a non-empty path that ends at level ground.

If the path starts with $\nearrow$, then we can look at the first time at which it returns to level ground, and decompose the path accordingly: $\nearrow x \searrow y$, where $x$ is a path that never goes below level ground, and $y$ is an arbitrary path that ends at level ground. Hence we need a way to capture paths that end at level ground and never go below level ground. Such a path can also be decomposed uniquely as $\nearrow x \searrow y$, where this time both $x$ and $y$ never go below level ground.

The considerations above lead to the following unambiguous grammar: $$ \begin{align*} &S \to aAbS' \mid bBaS' \\ &S' \to aAbS' \mid bBaS' \mid \lambda \\ &A \to aAbA \mid \lambda \\ &B \to bBaB \mid \lambda \end{align*} $$

As a somewhat degenerate example, the derivation tree for $abab$ is: Third tree

The proof that this grammar is unambiguous goes along the description above, though the formal proof by induction is somewhat challenging.


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