# Intersection of two NPDAs

Is there a way to take the interection of two NPDAs?

I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.

• Possible interesting follow-up question: if we know that the intersection of the two languages is context-free, can we compute a PDA for it?
– Raphael
Mar 26, 2014 at 8:50
• @Raphael, while I agree that it's interesting, I have not the faintest clue of how to go about finding it. Also, I might be naive, but can't a PDA be found for all context-free languages? Mar 26, 2014 at 10:06
• Me neither! This question was not intended for you, but maybe for you to ask on the site? It's certainly true that there is a PDA for the intersection (if it's context-free) but whether you can compute if from PDA of the original languages is not clear. See for instance this answer: even if we know that the language of a given PDA is in DCFL, we can not compute a DPDA for it.
– Raphael
Mar 26, 2014 at 10:28

The intersection of two context-free languages can be non-context-free. The classical example is $$\{ a^n b^n c^m : n,m \geq 0 \} \cap \{ a^m b^n c^n : n,m \geq 0 \} = \{ a^n b^n c^n : n \geq 0 \}.$$ So in general you cannot simulate the intersection of two NPDAs with an NPDA.