-3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Welcome back to Computer Science Stack Exchange today! Since this question has a highly upvoted answer, and our goal is to build a library of useful questions and answers, I hope you are willing to improve this question. This means rewrite the question in the form of an actual question, use more descriptive title, use correct tags, add some context, show us your research at the time, and an explanation why you think it didn't work. Thank you. $\endgroup$ Jan 25 at 14:32

1 Answer 1

11
$\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$
2
  • $\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 you have read our privacy policy.

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