0
$\begingroup$

Construct the CFG given the following language:

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

$\endgroup$

closed as unclear what you're asking by Yuval Filmus, Evil, David Richerby, dkaeae, vonbrand Jun 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.

  • 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.