# Constructing PDA with either one state or two states

If $L$ is a context-free language and $\epsilon \notin L$, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no $\epsilon$-moves ?

• In what form is the language given to you? – Tara B Apr 6 '13 at 19:58
• @TaraB : Hey, thanks for the question. I just edited the post accordingly. You're only required to prove that there exists such an automaton. – Enigman Apr 7 '13 at 3:38
• Ah, right. That renders my question irrelevant! It also means I know how to give a hint now. – Tara B Apr 7 '13 at 12:56

Hint: Take a context-free grammar in Chomsky normal form for $L$ and think about how you might be able to use this to construct the PDA in question. (You can use the stack to perform the derivations, essentially.)
• Yes, it would. Sorry, I hadn't thought through the part about no $\epsilon$-transitions properly. – Tara B Apr 7 '13 at 17:06