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$
2
  • $\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$ Commented Apr 24, 2017 at 19:23
  • $\begingroup$ Related question. Proving ambiguity, on the other hand, is trivial. Proving that a language is inherently ambiguous is arduous. $\endgroup$ Commented Apr 24, 2017 at 19:57

1 Answer 1

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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.