0
$\begingroup$

How can I describe a Push Down Automaton that recognize the language $P=\{a^{2^n} | n \geq 0 \}$?

My approach

I know that the language can be described by a Turing Machine, but how i can the stack recognize that language?

$\endgroup$
  • 1
    $\begingroup$ This is impossible. You can show it is not context-free by applying the Pumping Lemma. $\endgroup$ – Hendrik Jan Oct 1 '17 at 14:13
  • $\begingroup$ Existence of a TM accepting a language $L$ does not guarantee existence of a PDA accepting this language. Please look here. $\endgroup$ – fade2black Oct 1 '17 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.