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 ?


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

  • $\begingroup$ Thank you for the answer. $\endgroup$ – stefanie Nov 25 '17 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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