Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

Question

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the proof of the statement that the intersection of a CFL and a regular language is again CFL.

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book Introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

Answer 1

Take some time to browse the book. Sipser has the result, but stated as Problem 2.30a. Luckily an answer is provided. (In my (third) edition it is Problem 2.18a, from which I quote below.)

"[...] we construct a PDA $P'$ that recognizes $C\cap R$ with the set of states $Q\times Q'$. $P'$ will do what $P$ does and also keep track of the states of $D$. [...]"

Answer 2

There is a simple proof using context-free grammars. Let $L$ be a context-free language with context-free grammar $\langle V,T,P,S \rangle$, and let $R$ be a regular language with DFA $\langle \Sigma,Q,q_0,F,\delta \rangle$. We construct a new context-free grammar whose nonterminals consist of a new start symbol $S'$ and the triples in $Q \times V \times Q$. The idea is that $\langle q_1,A,q_2 \rangle$ generates all words $w \in L(A)$ such that $\delta(q_1,w) = q_2$.

Let us assume, without loss of generality, that the grammar is in Chomsky normal form: all rules are of the form $A \to BC$, $A \to a$, $S \to \epsilon$; and $S$ doesn't appear on the right-hand side of a rule. We can carry out the construction even without this simplifying assumption – that's a good exercise for you.

The rules of the new grammar are:

1. For every $q \in F$: $S' \to \langle q_0, S, q \rangle$.
2. If $S \to \epsilon$ is a rule and $q_0 \in F$: $S' \to \epsilon$.
3. For every rule $A \to a$ and for every $q \in Q$: $\langle q,A,\delta(q,a) \rangle \to a$.
4. For every rule $A \to BC$ and for every $q_1,q_2,q_3 \in Q$: $\langle q_1,A,q_3 \rangle \to \langle q_1,B,q_2 \rangle \langle q_2,C,q_3 \rangle$.

Correctness proof left to you.

Answer 3

I don't know of a simple proof, but there is a proof where the underlying idea is simple to understand.

Suppose you have a PDA $N$ (deterministic or nondeterministic; doesn't matter) which accepts the language $L_M$, and whose set of states is $S$. And further suppose you have a DFA $M$ with $T$ as its set of states which accepts the language $L_M$.

Conceptually, you can construct a new PDA, whose set of states is the Cartesian product $S \times T$, and awhich "runs" both the PDA and the DFA in parallel. A transition from state $(s_i,t_j)$ to state $(s_p,t_q)$ does whatever the PDA does when transitioning from state $s_i$ to $s_p$, but also takes the appropriate transition from $t_j$ to $t_q$.

An accept state in this new PDA is any state which corresponds to an accept state in both $M$ and $N$. Then this PDA should, assuming we get the details right, accept the language $L_M \cap L_N$.

There are a lot of details that you need to get right, which makes the proof fairly technical. So it's not a short proof. But it's simple to understand the idea behind it.

If you want to understand how this works, I would suggest trying to write a reasonably formal proof that the intersection of two regular languages is regular using a similar construction.

And as an additional exercise: Why can't you use this technique to prove that the intersection of two context-free languages is context-free?

Answer 4

We should imagine the way a pushdown automaton (PDA) works.

A PDA has a read-only head pointing at the input string. At each moment, it is resting at some index of the input string. And while the PDA is still running, it only moves from left to right once. But it may stay at some indices to "think" for a while.

Having said that, we can see that there are two kinds of transitions:

1. Consuming transition: the transitions that moves the input head one step to the right.

2. Non-consuming transition: the transitions that keeps the input head in place. These ones only manipulate the stack for sure.

Now, construct the cross product of the PDA $\mathbb{P}$ and the DFA $\mathrm{A}$ as usual, i.e. with the set of states as cartesian product of the set of states of $\mathrm{P}$ and the set of states of $\mathrm{A}$.

So, for each consuming transition of $\mathbb{P}$, we only allow it in the cross product PDA when the corresponding transition in $\mathrm{A}$ is also true.

---

And while the PDA is "thinking" (i.e. performing non-consuming moves), the DFA $\mathrm{A}$'s state must remain unchanged.