-3
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • $\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 '18 at 21:28
  • $\begingroup$ @supercat Automata that read a letter at each computational step are usually called "real-time" automata. $\endgroup$ – Hendrik Jan Oct 25 '18 at 20:10

Your Answer

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

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