# Convert this language to Context Free Grammar

I'm having trouble understanding how to convert this language to context free grammar.

$$\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$$

Part im getting stuck on is how to deal with a and c, whenever a c is added, you must also add an a, but with them at opposite ends of the string how do you properly build grammar for it? Since the below is not possible:

\begin{align} C &\rightarrow aC \\ C &\rightarrow c \end{align}

I've read the below post many times and tried to apply it but still not able to get it.

How to prove that a language is context-free?

Someone able to show me how this can be done?

• Did you try making a PDA for this language? Because, making a PDA is relatively easier than directly coming up with a CFG. – SiluPanda Apr 29 at 10:18

If you need to prove the language is context-free, showing a PDA that accepts $$L$$ is enough.

Sometimes, formulating the rules that generate exactly the language $$L$$ is not so trivial; in such cases you can start by a constructing the PDA that accepts $$L$$, then convert it to a CFG.

The transformation PDA $$\rightarrow$$ CFG can be found:

Lecture notes

Answer on this site

Whenever a $$c$$ is added, you must also add an $$a$$, but with them at opposite ends of the string how do you properly build grammar for it?

The production rule you are looking for looks like the following,

$$X\to aXc.$$

The full context-free grammar for the given language can be

$$S\to aS \mid aSc \mid a \mid ab \mid abb \mid abbb.$$