0
$\begingroup$

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?

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.