2
$\begingroup$

As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$. That was not so hard, I found a grammar which I think is correct:

$S \longrightarrow bA \mid aB$

$A \longrightarrow a \mid aS \mid bAA$

$B \longrightarrow b \mid bS \mid aBB$

Though then I found out that this grammar is ambiguous.

So the question is, is there any context free grammar generating language $L$ that is not ambiguous? I've read that there is no algorithm to determine whether a grammar is ambiguous. So if there is such grammar, how can we prove it is? Or is there any way to transform my grammar $G$ to become unambiguous?

$\endgroup$
  • $\begingroup$ There are ways of proving that a context-free language is inherently ambiguous, but your language is not inherently ambiguous. You just have to think of a different grammar. $\endgroup$ – Yuval Filmus Apr 24 '17 at 19:23
  • $\begingroup$ Related question. Proving ambiguity, on the other hand, is trivial. Proving that a language is inherently ambiguous is arduous. $\endgroup$ – Raphael Apr 24 '17 at 19:57
3
$\begingroup$

You can get an unambiguous grammar by thinking of words in $L$ as walks that start and end on the Y axis; each $a$ corresponds to a move $\nearrow$, and each $b$ corresponds to a move $\searrow$. Each such walk can be decomposed into segments of the form $\nearrow \cdots \searrow$ and $\searrow \cdots \nearrow$ which only touch the Y axis at the endpoints. Moreover, this decomposition is unique.

In turn, in a walk of the form $\nearrow \cdots \searrow$, the $\cdots$ part is itself a concatenation of walks of the same form, and this decomposition is unique. Alternatively, if you convert $\nearrow \mapsto ($ and $\searrow \mapsto )$, then walks of the form $\nearrow \cdots \searrow$ become valid strings of balanced parenthesis, surrounded by a pair $()$.

Putting everything together, we get the following unambiguous grammar: $$ \begin{align*} &S \to AS \mid BS \mid \epsilon \\ &A \to a X b \\ &X \to AX \mid \epsilon \\ &B \to b Y a \\ &Y \to BY \mid \epsilon \end{align*} $$ Actually proving that this grammar generates $L$ and that it is unambiguous is tedious, and left to you.

$\endgroup$

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.