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!

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

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.

  • $\begingroup$ thank you, I also just realized that the number of a's must be equal to the number of c's. $\endgroup$ – Harvat Apr 2 '14 at 11:02
  • $\begingroup$ 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 $\endgroup$ – Harvat Apr 2 '14 at 11:10
  • $\begingroup$ 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$. $\endgroup$ – frabala Apr 2 '14 at 11:12

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.