Li n L2 = Li и L2

and the CFLs are closed under union, it would follow that the CFLs are closed under intersection. However, we know they are not from Example 7.26.

Lastly, let us prove (3). We know S* is a CFL for every alphabet S; designing a grammar or PDA for this regular lemguage is easy. Thus, if Ly - L2 were always a CFL when L\ and L2 are, itwould follow that S* - L was always a CFL when L is. However, E* - L is L when we pick the proper alphabet E. Thus, we would contradict (2) and we have proved by contradiction that Lj - L2 is not necessarily a CFL. □

7.3.5 Inverse Homomorphism

Let us review from Section 4.2,4 the operation called inverse homomorphism, If Л is a homomorphism, and L is any language, then (L) is the set of strings w such that h{w) is in L. The proof that regular languages are closed under inverse homomorphism was suggested in Fig, 4.6. There, we showed how to design a finite automaton that processes its input symbols a by applying a homomorphism h to it, and simulating another finite automaton on the sequence of inputs h{a).

We can prove this closure property of CFLs in much the same way, by using PDAs instead of finite automata. However, there is one problem that we face with PDAs that did not arise when we were dealing with finite automata. The action of a finite automaton on a sequence of inputs is a state transition, and thus looks, as far as the constructed automaton is concerned, just like a move that a finite automaton might make on a single input symbol.

When the automaton is a PDA, in contrast, a sequence of moves might not look like a move on one input symbol. In particular, in n moves, the PDA can pop n symbols off its stack, while one move can only pop one symbol. Thus,

Since we know that the CFLs are not closed under intersection, but are closed under intersection with a regular language, we also know about the set-difFerence and complementation operations on CFLs. We summarize these properties in one theorem.

Theorem 7.29: The following are true about a CFLs L, Li, and L2, and a regular language R.

1. L - Rls a context-free language.

2. L is not necessarily a context-free language.

3. Li - L2 is not necessarily context-free.

PROOF: For (1), note that L - R = L nR. If Я is regular, so is R regular by Theorem 4.5. Then L - Ris a CFL by Theorem 7,27.

For (2), suppose that L is always context-free when L is. Then since

the construction for PDAs that is analogous to Fig. 4.6 is somewhat more complex; it is sketched in Fig. 7.10, The key additional idea is that after input a is read, h{a) is placed in a buffer, The symbols of h{a) are used one at a time, and fed to the PDA being simulated. Only when the buffer is empty does the constructed PDA read another of its input symbols and apply the homomorphism to it. We shall formalize this construction in the next theorem.

Input

Accept/ reject

Stack

Figure 7.10: Constructing a PDA to accept the inverse homomorphism of what a given PDA accepts

Theorem 7,30: Let L be a CFL and h a homomorphism. Then h (L) is a CFL.

PROOF: Suppose h applies to symbols of alphabet S and produces strings in T*. We also assume that L is a language over alphabet T. As suggested above, we start with a PDA P - {Q,T,T,S,qo, Zq, F) that accepts L by final state. We construct a new PDA

F-(g,S,(S,(?o,e),Zo,Fx{e}) (7.1)

where:

1. Q is the set of pairs (qx) such that:

(a) g is a state in Q, and

(b) a; is a suffix (not necessarily proper) of some string h{a) for some input symbol a in E.

That is, the first component of the state of P is the state of F, and the second component is the buffer. We assume that the buffer will periodically be loaded with a string h{a), and then allowed to shrink from the front, as we use its symbols to feed the simulated PDA F. Note that since S is finite, and h{a) is finite for all a, there are only a finite number of states for P.

2. S is defined by the following rules:

(a) S{{q,i),a,X) = {(g,ft(a}),AT} for all symbols a ui S, all states q in Q, and stack symbols X in Г. Note that a cannot be e here. When the buffer is empty, P can consume its next input symbol a and place h{a) in the buffer.

(b) If 6{q, b,X) contains (p,7), where f is in T or 6 = e, then

S{{q,bx),t,X)

contains ((p,x),7). That is, F always has the option of simulating a move of F, using the front of its buffer. If 6 is a symbol in T, then the buffer must not be empty, but if b = e, then the buffer can be empty.

3. Note that, as defined in (7.1), the start state of P is (go,e); i.e., P starts in the start state of P with an empty buffer.

4. Likewise, the accepting states of P, as per (7.1), are those states {q,e) such that q is axi accepting state of P.

The following statement characterizes the relationship between P and P:

{qo,h{w),Zo) r (p,e,7) if andonly if ((9o,e),w, Zo) 1, ((p,e),p,7).

The proofs in both directions ги-е inductions on the number of moves made by the two automata. In the if portion, one needs to observe that once the buffer of F is nonempty, it cannot read another input symbol and must simulate F, until the buffer has become empty (although when the buffer is empty, it may still simulate F). We leave further details as an exercise.

Once we accept this relationship between F and F, we note that F accepts h(w) if and only if P accepts w, because of the way the accepting states of F are defined. Thus, L(F) = fr (L(F)). □

7.3.6 Exercises for Section 7.3

Exercise 7.3.1: Show that the CFLs are clo.sed under the following operations:

a) init, defined in Exercise 4.2.6(c). Hint: Start with a CNF grammar for the language L.