Construct the CFG given the following language:
$$\{a^i \; b^j \; c^k \;|\; i = j \; or \; j = k \}$$
0
-
1$\begingroup$ What have you tried? Where did you get stuck? This is not a homework-answering service. Your question is routine, and you should be able to solve it on your own. $\endgroup$ – Yuval Filmus Jun 16 at 10:40
-
$\begingroup$ Hint: Your language is the union of $\{ a^i b^i c^k : i,k \geq 0 \}$ and $\{a^i b^k c^k : i,k \geq 0 \}$. $\endgroup$ – Yuval Filmus Jun 16 at 10:40
-
1$\begingroup$ You are right I was lazy. I tried on my own and I think I figured it out. $\endgroup$ – ElDon90 Jun 16 at 10:44
-
$\begingroup$ See below @YuvalFilmus, Thanks $\endgroup$ – ElDon90 Jun 16 at 10:52
0
$\begingroup$
$\endgroup$
Hint: Set up a grammar to get $i = j$ or $j = k$, then tweak to make sure the equality can't hold.
-
$\begingroup$ I'm not sure you can do the tweaking. If memory serves, this is a canonical example of an inherently ambiguous context-free language. $\endgroup$ – Yuval Filmus Jun 20 at 13:37
-
$\begingroup$ @YuvalFilmus, you can do it. Write sub-grammars for $a^i b^i c^k$, "fix" the $a^i b^i$ part to ensure equality isn't possible; mirror image gives $a^i b^j c^j$ and different number of $b$ and $c$. The ambiguity isn't an issue here. $\endgroup$ – vonbrand Jun 20 at 14:52
0
$\begingroup$
$\endgroup$
The answer should be the following:
$$ \begin{align} &S \to WQ \mid XY \\ &W \to aW \mid ε \\ &Q \to bQc \mid ε \\ &X \to aXb \mid ε \\ &Y \to cY \mid ε \end{align} $$
-
1$\begingroup$ Please, let them do their own homework. You're making life harder for teachers. $\endgroup$ – reinierpost Jun 17 at 12:31
