Context Free Grammar

1.1k Views Asked by At

How can a context free grammar be generated for the following language:

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

I assume that any production rule that places a $b$ or $c$ must also place an $a$ but I don't know how to do this while maintaining order.

2

There are 2 best solutions below

4
On BEST ANSWER

Start generating $c$s and $a$s, by say the rule $S \to aSc$ ($S$ the start variable), we need a possibility to switch to $b$s, by say $S \to T$. The rule $T \to aTb$ will generate $a$s and $b$s, and $T\to \epsilon$ (the empty word) will allow us to stop. So our grammar is $\{S \to aSc|T, T \to aTb|\epsilon\}$.

2
On

You can just reduce that to a single production as S -> aSc | aSb | ab

I hope I am correct.