4
$\begingroup$

I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's.

I have come up with a couple of possibilties so far. I think they're correct but they're all ambiguous, and I want the grammar to be non-ambiguous, this is one option:

S -> aX | bY | ε

X -> bS

Y -> aS

This is another one:

S -> aSb | bSa | SS | ε

And another one:

S -> aSb | bSa | abS | baS | ε

These grammars can generate the word ab in at least two different ways, for example, so they are ambiguous.

Is there any "tip" or "way" to eliminate ambiguity in a context free grammar such as this one?

Thanks for your time and have a nice day! :D

$\endgroup$
3
  • $\begingroup$ 1) Your first grammar is regular, which can't be right (the language is not regular). 2) The second one can't generate abba. Also, rules of the form $S \to SS$ are poison for unambiguity. 3) In general deciding ambiguity is undecidable hence there's no easy algorithm to get rid of it. $\endgroup$
    – Raphael
    Nov 19, 2017 at 11:22
  • $\begingroup$ Hint: you can use non-linear rules. For instance, there are simple unambiguous grammars for the Dyck language. $\endgroup$
    – Raphael
    Nov 19, 2017 at 11:26
  • $\begingroup$ There is no a universal rule to eliminate ambiguity from a CFG. Each grammar may require a unique approach. For example, to git rid of ambiguity in the CFG for math expressions in a programming languages we introduce operator precedence: first unary operator, then mul and div, and then add and sub. $\endgroup$
    – fade2black
    Nov 19, 2017 at 11:43

1 Answer 1

5
$\begingroup$

There is no general trick — indeed, given a context-free grammar, it is undecidable to determine whether it is ambiguous or not, and it is also undecidable to determine whether the language it generates is inherently ambiguous or not, see for example this answer on cstheory.

In your case, one way to go is to think of $a$ as corresponding to $\nearrow$ and of $b$ as corresponding to $\searrow$. We are interested in paths that start and end on the $x$ axis, for example $$ \begin{array}{cccccc} & \nearrow & \searrow \\ \nearrow & & & \searrow \\\hline & & & & \searrow & \nearrow \end{array} $$ We can decompose every such non-empty path into a first part, which ends the first time that the path reaches back to the $x$ axis, and the rest. If the first part starts with $\nearrow$, then it ends with a $\searrow$ and in between there is a path which never dips below where it started. We can denote such a path by $\top$. Any such path is either empty, or can be decomposed into a first part ending when the path reaches back to the initial level, followed by another $\top$ part. Putting everything together (and consider also the case in which the first part starts with $\searrow$), we obtain the following unambiguous context-free grammar (which for brevity is over $\nearrow,\searrow$): $$ \begin{align*} & S \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow S \mid \color{red}\searrow \bot \color{red}\nearrow S \\ & \top \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow \top \\ & \bot \to \epsilon \mid \color{red} \searrow \bot \color{red}\nearrow \bot \end{align*} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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