Problem Detail: I urgently need a language which can be recognised by 2 PDA’s but not with 1 PDA.
Asked By : nurgasemetey
Answered By : Hendrik Jan
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 nge 1 }$ and $L_2 = { a^nb^ma^nb^m mid m,nge 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 nge 1}$ is another example of a non-context-free language. By my earlier remark ${ ww mid win {a,b}^* }$ is another example, and makes a nice puzzle.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11925
