Context Free Grammar for natural numbers

784 Views Asked by At

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!

1

There are 1 best solutions below

3
On BEST 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.