0
$\begingroup$

Construct the CFG given the following language:

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

$\endgroup$
  • 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$

Hint: Set up a grammar to get $i = j$ or $j = k$, then tweak to make sure the equality can't hold.

$\endgroup$
  • $\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$

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

$\endgroup$
  • 1
    $\begingroup$ Please, let them do their own homework. You're making life harder for teachers. $\endgroup$ – reinierpost Jun 17 at 12:31

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