I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA.


1 Answer 1


A machine using two pushdowns accepts the recursively enumerable languages. So there is a lot to choose from. Look for your favourite non-context-free language, and build a two-stack machine for it!

(added. see also the answer obtained via our sistersite math) The languages $L_1 = \{ a^nb^nc^n \mid n\ge 1 \}$ and $L_2 = \{ a^nb^ma^nb^m \mid m,n\ge 1 \}$ are typical examples of non-context-free languages. They are easily recognized using two pushdowns. E.g., for $L_1$ store the number of $a$'s on both stacks; it can then be used to check both the number of $b$'s and $c$'s.

We can also shift the symbols from one stack to the other while doubling them. staring with $1$, and iterating we obtain powers of two. Note $\{a^{2^n} \mid n\ge 1\}$ is another example of a non-context-free language.

By my earlier remark $\{ ww \mid w\in \{a,b\}^* \}$ is another example, and makes a nice puzzle.

  • $\begingroup$ Is there any term for the category of languages a two-stack machine could process if every path through a state loop was required to consume at least one character from the input stream (as opposed to the stacks)? It could process some languages that a pushdown automaton could not, like aⁿbⁿcⁿ, but would be fully decidable, unlike a full Turing machine. $\endgroup$
    – supercat
    Oct 24, 2018 at 21:28
  • $\begingroup$ @supercat Automata that read a letter at each computational step are usually called "real-time" automata. $\endgroup$ Oct 25, 2018 at 20:10

Your Answer

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

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