2
$\begingroup$

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 ?

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

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

$\endgroup$
  • $\begingroup$ Wouldn't Greibach Normal form make more sense? $\endgroup$ – Enigman Apr 7 '13 at 14:54
  • $\begingroup$ Yes, it would. Sorry, I hadn't thought through the part about no $\epsilon$-transitions properly. $\endgroup$ – Tara B Apr 7 '13 at 17:06

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.