1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @HendrikJan Wow! I totally overlooked that one. As stupid as this may sound, but it seems too easy to be true.... Am I missing something? $\endgroup$ – Does it matter Oct 27 '18 at 17:15
  • 1
    $\begingroup$ That is called your Aha! moment. Once you see it, you cant believe you missed it first time. Now there are only formalities to write the details. $\endgroup$ – Hendrik Jan Oct 27 '18 at 17:20
  • $\begingroup$ @HendrikJan Can you leave your first reply as an answer to my question? I can then accept it because it's exactly what I needed. You could also add that it can also be Problem 2.30A in some other versions of the book ;). Thank you! $\endgroup$ – Does it matter Oct 27 '18 at 17:45
3
$\begingroup$

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$. [...]"

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ For the additional exercise, it is obviously impossible to merge two stacks, which may differ vastly in length when the two PDAs run. $\endgroup$ – Thinh D. Nguyen Oct 27 '18 at 12:24
  • 1
    $\begingroup$ This exercise may help the OP if he/she already understands what is going on in the proof for DFA. But of no help, when he/she still has not figured out the cross product in your answer. Because, in that case, there is no second stack to be added to the picture. $\endgroup$ – Thinh D. Nguyen Oct 27 '18 at 12:26
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.