Consider the proof given below. Why does this construction not work for intersection of two CFLs?
Intersection with Regular Languages Proposition 3. If L is a CFL and R is a regular language then LnR is a CFL. Proof. Let P be the PDA that accepts L, and let M be the DFA that accepts R. A new PDA P will simulate P and M simultaneously on the same input and accept if both accept. Then P' accepts LnR The stack of P is the stack of P . The state of P at any time is the pair (state of P, state of M) o These determine the transition function of P . The final states of P' are those in which both the state of P and state of M are accepting More formally, let M-(Q1 , 11, F1) be a DFA such that L (M)-R and P-(Q2, 2-2, F2) be a PDA such that L(P) L. Then consider P, Q. ., 40, F) such that 2 6((P. q), x, a) = {((p', q'), b) l p, = 1 (p, x) and (q, b) E 2(g, x, a)) One can show by induction on the number of computation steps, that for any w 2 The proof of this statement is left as an exercise. Now as a consequence, we have w E L(P') iff ,e) P, p, q), such that (p.4) e F (by definition of PDA acceptance) iff qo, e) P' ((p, ), a) such that pe Fi and q E F2 (by definition of F) iff q1 >M p and (q2,e) >p (q, a) and p E F1 and q e F2 (by the statement to be proved as exercise) iff w L(M) and w E L(P) (by definition of DFA acceptance and PDA acceptance) aIl Why does this construction not work for intersection of two CFLs? Intersection with Regular Languages Proposition 3. If L is a CFL and R is a regular language then LnR is a CFL. Proof. Let P be the PDA that accepts L, and let M be the DFA that accepts R. A new PDA P will simulate P and M simultaneously on the same input and accept if both accept. Then P' accepts LnR The stack of P is the stack of P . The state of P at any time is the pair (state of P, state of M) o These determine the transition function of P . The final states of P' are those in which both the state of P and state of M are accepting More formally, let M-(Q1 , 11, F1) be a DFA such that L (M)-R and P-(Q2, 2-2, F2) be a PDA such that L(P) L. Then consider P, Q. ., 40, F) such that 2 6((P. q), x, a) = {((p', q'), b) l p, = 1 (p, x) and (q, b) E 2(g, x, a)) One can show by induction on the number of computation steps, that for any w 2 The proof of this statement is left as an exercise. Now as a consequence, we have w E L(P') iff ,e) P, p, q), such that (p.4) e F (by definition of PDA acceptance) iff qo, e) P' ((p, ), a) such that pe Fi and q E F2 (by definition of F) iff q1 >M p and (q2,e) >p (q, a) and p E F1 and q e F2 (by the statement to be proved as exercise) iff w L(M) and w E L(P) (by definition of DFA acceptance and PDA acceptance) aIl Why does this construction not work for intersection of two CFLs
