Similar to the encoding of a Turing Machine, we can encode a Push-Down Automata. Denote $\langle M \rangle$ as the encoding of PDA M, and a natural number n, is language $L = \{ \langle M \rangle | \text{ M is a PDA, L(M) contains at least 1 string w that } |w| \leq n \}$ a recursive language?


By the definition of a recursive language, I have to prove that there exists a Turing Machine that can accept L and for any input string x, the TM will end up in a halt state.

But how exactly should I do to find/construct that? Or I don’t really have to construct a Turing Machine but use some existing theorem?


1 Answer 1


You should think in algorithms instead of thinking in Turing Machine. Turing Machines are just a very formal way to express algorithms but writing a Turing Machine even for simple algorithms is a chore.

It suffices to know that if one really wanted to, they could construct a very complicated Turing Machine to encode an algorithm.

What the question is really asking is "Is there an algorithm that, given a PDA $M$ and an integer $n$, decides if $L(M) \cap \Sigma^{\leqslant n}\neq \emptyset$?".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.