# Context Free Grammar for natural numbers

this is the problem:

Generate a Context Free Grammar for the language $L_1 := \{{a^nb^3c^n | n\in\mathbb N}\}$

I'm not so sure about my solution, is this correct?:

$G=(\sum,V,S,P)$

$\sum : = \{{a,b,c}\}$

$V : = \{{S,X,Y}\}$

$S : = \{{S}\}$

$P : = \{{S\rightarrow aSc | bbb}\}$

Thanks for help!

• This solution produces also $abbbccc$, which is not in the language. – frabala Apr 2 '14 at 10:52

## 1 Answer

The rules in your solution will produce words of the form $a^n b^3 c^m$, where probably $n\neq m$, because there is no constraint about how many $c$'s will be produced when there are produced $n$ numbers of $a$'s.

A solution could be $$S\to a S c~|~ bbb$$ This way you make sure that the string will have as many $a$'s as $c$'s and in the end of the production it gets three $b$'s in the middle of the $a$'s and the $c$'s.

• thank you, I also just realized that the number of a's must be equal to the number of c's. – Harvat Apr 2 '14 at 11:02
• this solution only works when I have n=0 or n=1, but how do I add the other cases such as aabbbcc to the solution? - ok I got it now S gets replaced by aSc everytime – Harvat Apr 2 '14 at 11:10
• It works for every $n\in\mathbb{N}$. You can use the rule $S\to aSc$ as many times as you want. For example, you can use it two times $S\to aSc\to aaScc$ and then you can use rule $S\to bbb$, so in the end you produce $aabbbcc$. – frabala Apr 2 '14 at 11:12