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

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.

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:

• For every $q \in F$: $S' \to \langle q_0, S, q \rangle$.

• If $S \to \epsilon$ is a rule and $q_0 \in F$: $S' \to \epsilon$.

• For every rule $A \to a$ and for every $q \in Q$: $\langle q,A,\delta(q,a) \rangle \to a$.

• 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.

StackExchange Computer Science Q#99164, answer score: 5