patternMinor
Intersection of two NPDAs
Viewed 0 times
npdastwointersection
Problem
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.
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.
Solution
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.
$$ \{ 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.
Context
StackExchange Computer Science Q#23056, answer score: 6
Revisions (0)
No revisions yet.