Construct context - free grammar

244 Views Asked by At

The question was to construct context - free grammar whose language is

$$L = \{ a^i b^j c^k | 0 \leq i + k \leq j \}$$

My answer was

$$S \rightarrow a A c $$

$$A \rightarrow a b b B c $$

$$B \rightarrow b b $$

But when I check the string it only gives $aabbbbcc$. Does my answer gives the correct CFG ?

1

There are 1 best solutions below

1
On BEST ANSWER

You can write $i+k+n=j\quad$ so $\quad a^ib^jc^k=(a^ib^i)(b^n)(b^kc^k)$

To generate $a^ib^i$ we need $\begin{cases}A\\A\to aAb\\A\to\epsilon\end{cases}$

To generate $b^n$ we need $\begin{cases}B\\B\to bB\\B\to\epsilon\end{cases}$

To generate $b^kc^k$ we need $\begin{cases}C\\C\to bCc\\C\to\epsilon\end{cases}$

And finally $S=ABC$.