I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered May 10, 2013 at 8:34
-
$\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$– supercatOct 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