1

I have to create the productions for a CFG that follows

$$\{a^ib^jc^k : j = i + k\}$$

I can get close to the answer. I found

$$\begin{align*} &A\to aAb \mid B\\ &B\to bBc \mid \epsilon \end{align*}$$

but that allows c's in the wrong place. I need help creating the productions.

Sams
  • 25

1 Answers1

1

the language L may be rewritten as $\{ a^ib^îb^kc^k \}$ - now it should be easier to come up with a grammar:

$ S \to AB \\ A \to aAb \,|\, \epsilon \\ B \to bBc \,|\, \epsilon $

collapsar
  • 344
  • Thanks! I thought I needed a variable on the end, but I couldn't figure out how to get it without having a bunch of them interspersed in the string. – Sams Apr 01 '14 at 03:03