15
$\begingroup$

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?

$\endgroup$
  • 12
    $\begingroup$ Consider .* as the regular language and its intersection with a context free one. $\endgroup$ – AProgrammer Dec 5 '13 at 14:31
  • 1
    $\begingroup$ It'd be the strings of the context free one. But those strings are also generated by the regular language, so it'd be a context free language which is also regular. $\endgroup$ – sanjeev mk Dec 5 '13 at 14:39
  • 8
    $\begingroup$ The language could be regular. But it usually isn't. Think again about the counterexample given by AProgrammer. It should probably be the answer. Every context free language is a subset of a regular language. It's true that the intersection of languages CF and REG will be accepted by DFA of REG, but it also matters what is rejected. $\endgroup$ – Karolis Juodelė Dec 5 '13 at 15:02
  • 3
    $\begingroup$ cs.stackexchange.com/q/59886/755 $\endgroup$ – D.W. Jun 22 '16 at 7:05
  • 1
    $\begingroup$ @D.W. Relevant but somebody's proposed it as a dupe and it's not that. This question is asking why the intersection isn't always regular; the other is asking why the intersection isn't always non-regular. The specific set-up of this question (talking about strings that are accepted by both a DFA and a PDA, so they're accepted by a DFA, so the language is regular, right?) means that answers to the other question don't really answer this one well. $\endgroup$ – David Richerby Jun 23 '16 at 9:55
20
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 I almost posted an answer that's equivalent to your last sentence. Frankly, the rest of the answer seems unnecessary. :) $\endgroup$ – Patrick87 Dec 5 '13 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.