20
$\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$
6
  • 12
    $\begingroup$ Consider .* as the regular language and its intersection with a context free one. $\endgroup$ Commented Dec 5, 2013 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
    Commented Dec 5, 2013 at 14:39
  • 9
    $\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$ Commented Dec 5, 2013 at 15:02
  • 3
    $\begingroup$ cs.stackexchange.com/q/59886/755 $\endgroup$
    – D.W.
    Commented Jun 22, 2016 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$ Commented Jun 23, 2016 at 9:55

1 Answer 1

22
$\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$
2
  • 2
    $\begingroup$ +1 I almost posted an answer that's equivalent to your last sentence. Frankly, the rest of the answer seems unnecessary. :) $\endgroup$
    – Patrick87
    Commented Dec 5, 2013 at 15:41
  • $\begingroup$ did not get "adding (q,a,[q]) arrows between matching states in P where the DFA has a arrows.". Unable to visualize how the product PDA will be. $\endgroup$
    – RajS
    Commented Nov 20, 2019 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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