# Help: Context Free Grammar [closed]

Construct the CFG given the following language:

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

## closed as unclear what you're asking by Yuval Filmus, Evil, David Richerby, dkaeae, vonbrandJun 20 at 13:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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