# Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$

I would like some help for the computation theory.

There is a PDA that accepts the language $$\{0^n 1^a 2^b \mid n = a+b\}$$, so how can I express it into context free grammar? Any help would be appreciated!

That's what I was trying, I am not sure if it is correct or not

S -> 0SA | 0SB | empty
A -> 1
B -> 2


Unfortunately your grammar generates mixed $$1$$s and $$2$$s.

You can try something like this:

$$S\rightarrow 0SB | S'$$
$$S' \rightarrow 0S'A | \varepsilon$$
$$A\rightarrow 1$$
$$B\rightarrow 2$$

Notice that I don't know if in your problem $$n$$ can be $$0$$ or not (and similarly for $$a$$ and $$b$$), so maybe you have to fix something.

Anyway, here the idea is starting generating first some $$0$$s an all the $$2$$s, and then add the remaining $$0$$s and the $$1$$s: it is similar to the "standard" grammar used to generate $$0^n 1^n$$.

• thank you for your help! – randomguy Dec 14 '20 at 23:40
• one more thing, can this context free grammar generate any regular lanuage ? and how should I determine if a context free grammar can generate a regular lanuage? Thanks for your help – randomguy Dec 14 '20 at 23:44
• Any regular language is generated by a CFG, but this specific grammar generates a single language, that is not regular (you van prove it using Pumping Lemma). There's no general algorithm to decide if a CFG actually generates a regular language, i.e., it's an undecidable problem. Anyway, once you have a specific CFG, there's some standard strategies (again, Pumping Lemma) to prove if the generated language is regular. Anyway, this question is interesting, and maybe deserves an other post. – user6530 Dec 14 '20 at 23:54
• oh, thank you so much! basically, by using the pumping lemma on the lanuage generated by CFG. Then, i will be able to see whether this particular CFG could generate a regular lanuage? thats a good tactic i have not thought about it. thanks for that – randomguy Dec 15 '20 at 0:11
• and i just want to clarify one thing: some of the CFG cannot generate the regular lanuage even CFG being more powerful than regular lanuage. – randomguy Dec 15 '20 at 0:13