Consider the following CFG:

$S\to AED | F \\ A \to Aa | a\\ B \to Bb | b\\ C \to Cc | c\\ D \to Dd | d\\ E \to bEc | bc\\ F \to aFd | BC$

The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,c) and $aaa...b^*c^*ddd...$ (equal number of a,d)

There is ambiguity since $abbccd$ can be derived respectively by $S\to AED$ and $S \to F$. I try to rewrite the production rule like: $$S\to AED\\E\to BC$$ But my CFG produces $a^*b^*c^*d^*$ which is different from original. Could anyone give me some tips?

  • $\begingroup$ IIRC, this is fairly close to a canonical example for inherently ambiguous languages. Intuitively, you can't handle the case "equal a,d and equal b,c" separately using context-free means, so the overlap is unavoidable. A formal proof might work along the lines of invoking the idea behind the pumping lemma twice (once for b,c and once for a,d) and noting that for some pair of "iteration" counts, the two loops have to derive to the same word. $\endgroup$ – Raphael Nov 4 '18 at 20:19
  • $\begingroup$ @Raphael: Yes, you can. You couldn't handle equal a,b and equal a,d separately, nor could you handle the requirement that all four have the same count, but you can certainly handle two non-interacting conditions separately. $\endgroup$ – rici Nov 4 '18 at 22:08
  • $\begingroup$ Ah, I think I had "equal a,c or equal b,d" in mind; that's the one, isn't it? This one here works out since the two conditions are properly nested, so to speak. My bad, thanks! $\endgroup$ – Raphael Nov 5 '18 at 22:16
  • $\begingroup$ @raphael: yes, intermingled is ambiguous, afaik. $\endgroup$ – rici Nov 5 '18 at 22:59

Basically you have $L = L_1 \cup L_2$ where $L_1 \cap L_2 \ne \emptyset$. So naively writing the two productions:

$$L \to L_1 \\ L \to L_2 $$ will create an ambiguity. What's needed is to create $Ḷ_1' = L_1 - L_2$ in order to use the CFG $$L \to L_1' \\ L \to L_2 $$ This produces the same language, resolving the ambiguities in favour of $L_2$.

Context-free languages are not closed under set difference, so this is not a general solution. But in this particular case there is no problem.

Suppose we start with the two languages $L_1 = \{ a^ib^jc^kd^i \}$ and $L_2 = \{ a^ib^jc^jd^k \}$, which are not disjoint since $\{a^ib^jc^jd^i\}$ is a subset of both.

So we define $$Ḷ_1' = L_1 - L_2 = \{ a^ib^jc^kd^i \mid j \ne k\}$$ and are pleased to observe that it is context-free:

$$\begin{align}L_1' &\to E \mid a \; L_1'\; d\\ E &\to B \mid C \mid b \; E \;c\\ B &\to b \mid B b \\ C &\to c \mid C c \end{align}$$

Meanwhile, $L_2$ is simply

$$\begin{align}L_2 &\to A\; F\; D \\ F &\to \lambda \mid b\;F\;c \\ A &\to \lambda \mid A a \\ D &\to \lambda \mid D d \end{align}$$


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.