I am trying to convert a regular language to a context free grammar. The language is $L=\{a^n b^m c^k |n=m\ or\ m\le k\}$, my solution is: assume $m,n,k\ge0$

$S\to AS|BS|\lambda$

$A\to aAb|Ac|ab$

$B\to Bc|Bbc|aB$

Is this correct? Can somebody explain why it is correct or not correct?


Let us get things straight...the language $L$ is not regular (you can check using Pumping lemma) Although the language is Context Free as it is the union of two CFLs.

The grammar does not correspond to the language since the non-terminal $B$ can not be terminated. So only way to termiante it and get a word of the language is $S=A^*$. But $A=aAb=aAcb=aabcb\notin L$

Correct grammar should be

$$S\to A|B$$ $$A\to Ac|aAb|\lambda$$ $$B\to aB|bBc|Bc|\lambda$$

Two non terminals $A$ and $B$ for the two CFLs whose union is $L$.


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.