we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset of type 3 grammar. Am I wrong?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ I removed the second question is it is unrelated to the first. I recommend you ask it in a separate post, but only after 1) computability was covered in your class (assuming you are taking one), 2) reading our related reference questions and 3) forming your own opinion. $\endgroup$– RaphaelCommented Jun 25, 2014 at 9:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
You need to check the definitions: type-3 (regular) is a (proper) subset of type-2 (context-free). Therewith, every type-3 language has a PDA that accepts it.
Essentially, you take a finite automaton for your type-3 language, add the stack but never use it. Up to minor definitory differences (e.g. w.r.t. acceptance), this gives you a PDA for the language. This is also one way to prove that all regular languages are context-free!