Systematic approach or algorithm for designing a pushdown automata that accepts a langauge

Question

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.

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