Intersection of context free with regular languages

Question Detail: 

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context free but not regular.

The language generated by such an intersection has strings that are accepted both by a PDA and a DFA. Since it is accepted by a DFA, shouldn't it be a regular language? Plus, if the intersection is regular, it also implies context free, since all regular languages are also context free.

Can someone explain to me why the language obtained by such an intersection is not regular?

Asked By : sanjeev mk

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18642

Answered By : Gilles

If $L$ is context-free then there is a PDA $\mathscr{P}$ that accepts it. If $M$ is regular then there is a DFA $\mathscr{F}$ that accepts it. The intersection language consists of the words that are recognized by $\mathscr{P}$ and $\mathscr{F}$.

Any word that is in the intersection is accepted by $\mathscr{F}$, but not all words that are accepted by $\mathscr{F}$ are in the intersection: only those that are also accepted by $\mathscr{P}$.

The cross product proof consists of constructing an automaton $\mathscr{P} \otimes \mathscr{F}$ which contains the mechanics of both $\mathscr{P}$ and $\mathscr{F}$, and which accepts only words for which both sides accept. The cross-product automaton is a PDA (and therefore the recognized language is context-free) — intuitively, because the cross product with an $n$-state DFA consists of taking $n$ copies of $\mathscr{P}$ and adding $(q,a,[q])$ arrows between matching states in $\mathscr{P}$ where the DFA has $a$ arrows. The result is not a finite automaton in general (not even a non-deterministic one) because the $\mathscr{P}$ part relies on the stack and this reliance does not go away in $\mathscr{P} \otimes \mathscr{F}$ in general.

A trivial example is that $\mathscr{A}^*$ is regular, and if $L$ is context-free but not regular then $L \cap \mathscr{A}^* = L$ is context-free but not regular.