# Help: Context Free Grammar [closed]

Construct the CFG given the following language:

$$\{a^i \; b^j \; c^k \;|\; i = j \; or \; j = k \}$$

• 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. – Yuval Filmus Jun 16 '19 at 10:40
• 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 \}$. – Yuval Filmus Jun 16 '19 at 10:40
• You are right I was lazy. I tried on my own and I think I figured it out. – ddon-90 Jun 16 '19 at 10:44
• See below @YuvalFilmus, Thanks – ddon-90 Jun 16 '19 at 10:52

Hint: Set up a grammar to get $$i = j$$ or $$j = k$$, then tweak to make sure the equality can't hold.
• @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. – vonbrand Jun 20 '19 at 14:52
\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}