0
$\begingroup$

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?

$\endgroup$
4
  • $\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, 2018 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, 2018 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, 2018 at 22:16
  • $\begingroup$ @raphael: yes, intermingled is ambiguous, afaik. $\endgroup$
    – rici
    Nov 5, 2018 at 22:59

1 Answer 1

1
$\begingroup$

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}$$

$\endgroup$

Your Answer

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

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