1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ thank you for your help! $\endgroup$ – randomguy Dec 14 '20 at 23:40
  • $\begingroup$ 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 $\endgroup$ – randomguy Dec 14 '20 at 23:44
  • $\begingroup$ 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. $\endgroup$ – user6530 Dec 14 '20 at 23:54
  • $\begingroup$ 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 $\endgroup$ – randomguy Dec 15 '20 at 0:11
  • $\begingroup$ 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. $\endgroup$ – randomguy Dec 15 '20 at 0:13

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.