I understand that designing automatons is mostly a creative process but, a month ago I was having a discussion with a classmate about designing a NPDA or a DPDA that accepts a non-trivial language (trivial meaning, it is straightforward to design a PDA that accepts it) and he gave me a solution while mentioning an algorithm that he used to arrive at said solution. his solution was correct but used nearly twice the number of states than my solution which was also correct (both solutions used NPDAs). unfortunately I don't have access to him to ask about what he meant by an algorithm, anymore.

I looked in both Sipser and Linz books and I didn't find anything about such an algorithm or systematic approach.

If you know of such thing please demonstrate with your own language of choice.

  • $\begingroup$ It is easy to convert a CFG to a PDA, so it suffices for you to know how to construct CFGs. Unfortunately, generally speaking it's a create process. $\endgroup$ Dec 24, 2017 at 14:59
  • $\begingroup$ Create = creative. $\endgroup$ Dec 24, 2017 at 19:23

1 Answer 1


Your question is something very natural, that comes up a lot when first encountering computational model. The main problem is that your question does not "compile":

You ask if there is an algorithm that constructs PDAs. What would be the input for such an algorithm? This is the main crux of the problem.

Until you specify that, you won't really have an answer. As Yuval commented, if you get a CFG as input, then there is an easy procedure to convert it to a PDA.

Let's look at the other extreme: suppose you are given a Turing Machine, and you just ask whether there exists a PDA for its language (even without constructing it). As it turns out, this problem is undecidable (it's an immediate consequence of Rice's theorem, but in fact it's neither in RE nor in coRE).

This problem is something that often comes up in designing computational models - how do we specify what we want? If we give a rich specification formalism, such as Turing machines, then things become undecidable. And if we give something too poor, such as CFGs, then the construction task becomes easy, but writing down the specification becomes the hard part, so it's debatable whether we actually did any good...


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.