It works similarly, but with A generating any string of Os, and Б generating matching strings of Is and 2s,

However, L - Li П L2. To see why, observe that Li requires that there be the same number of Os and Is, while L2 requires the numbers of Is and 2s to be equal. A string in both languages must have equal numbers of all three symbols and thus be in L.

If the CFLs were closed under intersection, then we could prove the false statement that L is context-free. We conclude by contradiction that the CFLs are not closed under intersection, □

On the other hand, there is a weaker claim we can make about intersection. The context-free languages are closed under the operation of intersection with a regular language. The formal statement and proof is in the next theorem.

Theorem 7.27: If X is a CFL and Л is a regular language, then L П Rls s. CFL.

PROOF: This proof requires the pushdown-automaton representation of CFLs, as well as the finite-automaton representation of regular languages, and generalizes the proof of Theorem 4.8, where we ran two finite automata in parallel to get the intersection of their languages. Here, we run a finite automaton in parallel with a PDA, and the result is another PDA, as suggested in Fig. 7.9.

Input

Accept/ reject

Stack

Figure 7,9: A PDA and a FA can run in parallel to create a new PDA Formally, let

P{Qp,-E,T,5p,qp,Zo,Fp)

be a PDA that accepts L by final state, and let

A = {QA,i:,SA,qA.FA) be a DFA for R. Construct PDA

P = [Qp X QA,>T,S,(qp,qA)>Zo,Fp X Fa) where 5[{q,p),a,X) is defined to be the set of all pairs ((r,e),7) such that:

1. 3 = блСр,а), and

2. Pair (r,7) is in 5p{q,a,X).

That is, for each move of PDA P, we can make the same move in PDA P, and in addition, we carry along the state of the DFA j4 in a second component of the state of P. Note that a may be a symbol of E, or a = e. In the former case, 5(p,a} = Sa{p), while if a = e, then 5{p,a) = p; i.e., A does not change state while P makes moves on с input.

It is an easy induction on the numbers of moves made by the PDAs that (9P,u),Zo) r (?,c,7) if and only if ((<?р,9л),ш,2о) , ({g,jp),e,7), where

p = S{pA,U}). We leave these inductions as exercises. Since (q,p) is an acceptmg state of P if and only if g is an accepting state of P, and p is an accepting state of .4, we conclude that P accepts w if and only if both P and A do; i.e., w is m LCiR. □

Example 7.28: In Fig. 6.6 we designed a PDA called F to accept by final state the set of strings of is and es that represent minimal violations of the rule regarding how ifs and elses may appear in С programs. Call this language L. The PDA F was defined by

Pf = {{p,q,r},{h]AZ,Xo},6F,P,Xo,{r}) where Sp consists of the rules:

1. 6p(j>,e,Xo) = {{q,ZXo)}.

2. er{q,i,Z) = {{q,ZZ)}.

3. 6p{q,e,Z) = {iq,c)}.

4. Sp{q,e,Xo) = {{r,e,e)}.

Now, let us introduce a finite automaton

A= {{s,t},{i,e},eA>s,{s,t})

that accepts the strings in the language of i*e*, that is, all strings of is followed by es. Call this language R. Transition function Sa is given by the rules:

a) SA{s,i) = s.

b) SA{s,e)=t.

c) SA{t,e) = t.

Strictly speaking, A is not a DFA, as assumed in Theorem 7,27, because it is missing a dead state for the case that we see input г when in state t. However, the same construction works even for an NFA, since the PDA that we construct is aUowed to be nondeterministic. In this case, the constructed PDA is actually deterministic, although it will die on certain sequences of input. We shall construct a PDA

P=i{p,Q,r] X {s,t],{i,e},{Z,XQ},5, (p,s),Xo,{r] x {s,t})

The transitions of S are listed below and indexed by the rule of PDA F (a number from 1 to 4) and the rule of DFA A (a letter a, b, or c) that gives rise to the rule. In the case that the PDA F makes an e-transition, there is no rule of A used. Note that we construct these rules in a lazy way, starting with the state of P that is the start states of F and A, and constructing rules for other states only if we discover that P can enter that pair of states.

1: S{(p,a),€,Xo)={{ig,s),ZXo)}. 2a: Siiq,8),i,Z) = {i{g,s),ZZ)}. ЗЙ: 6{iq,sle,Z) = {{{q,t),e)}.

4: 6{{д,8},е,Хо) = {((г, s),c)}. Note: one can prove that this rule is never exercised. The reason is that it is impossible to pop the stack without seeing an e, and as soon as P sees an e the second component of its state becomes t.

3c: S{{q,t),e,Z) = {{[q,tU)}. 4: 5{{q,tU,XQ) = {{{r,tU)}.

The language L П Л is the set of strings with some number of is followed by one more e, that is, {г e * n > 0}. This set is exactly those if-else violations that consist of a block of ifs followed by a block of elses. The language is evidently a CFL, generated by the grammar with productions S -J- iSe \ e.

Note that the PDA P accepts this language L п R. After pushing Z onto the stack, it pushes more Zs onto the stack in response to inputs i, staying in state (q, $). As soon as it sees and e, it goes to state {g, t) and starts popping the stack. It dies if it sees an i until Xq is exposed on the stack. At that point, it spontaneously transitions to state (r, t) and accepts. □