Algorithm that takes input desc. of two PDAs and outputs intersection of langs. recognized by two PDAs

145 Views Asked by At

Does there exist an algorithm which takes as input the descriptions of two pushdown automata, $P1$ and $P2$, and prints the description of another pushdown automaton which recognizes the intersection of the languages recognized by $P1$ and $P2$?

1

There are 1 best solutions below

0
On BEST ANSWER

In general the intersection of two CFLs is not context free. Can you come up with an example? Mouse over the grey area below for an example. (It is a theorem that the intersection of a context free language with a regular language is context free.)

So the description of a PDA recognizing $P_1 \cap P_2$ does not necessarily exist.

The go-to example for showing this is, let $$P_1 = \{a^n b^n c^*\} \text{ and } P_2 = \{a^* b^n c^n \}$$