Theorem 9.21: If La is the language for list A, then La is a context-free language.

PROOF; Let S be the alphabet of the strings on list A = wi,w2,... ,-Wk, and let I be the set of uidex symbols: / - {ai,аз,.. -,а}. The DPDA P we design to accept La works as foHows.

1. As long as P sees symbols in E, it stores them on its stack. Since all strings in E* are in La, P accepts as it goes.

2. As soon as a P sees an index symbol in /, say Ui, it pops its stack to see if the top symbols form luf, that is, the reverse of the corresponding string.

(a) If not, then the input seen so far, and any continuation of this input is in Хл. Thus, P goes to an accepting state in which it consumes all future inputs without changing its stack.

(b) If was popped from the stack, but the bottom-of-stack marker is not yet exposed on the stack, then P accepts, but remembers, in its state that it is looking for symbols in I only, and may yet see a string in La (which P will not accept). P repeats step (2) as long as the question of whether the input is in La is rmresolved.

(c) If wf was popped from the stack, and the bottom-of-stack marker is exposed, then P has seen an input in La- P does not accept this input. However, since any input continuation cannot be in L, P goes to a state where it accepts all future inputs, leaving the stack unchanged.

3. If, after seeing one or more symbols of T, P sees another symbol of £, then the input is not of the correct form to be in La. Thus, P goes to a state in which it accepts this and all future inputs, without changing its stack.

We can use La, Lb and their complements in various ways to show undecidability results about context-free languages. The next theorem summarizes some of these facts.

Theorem 9.22: Let G-[ and G-z be context-free grammars, and let Л be a regular expression. Then the following are undecidable:

a) IsL(Gi) nL(G2) = 0?

b) Is L(Gi) = L(G2)?

c) IsL(Gi) =L(E)?

d) Is L(G]) = T* for some alphabet T?

e) Let Gi be a CFG for (E U f)* and let G2 be a CFG for Tl U Lb- Then L{Gi) С L(G2) if and only if и Lb = (E U /)*, i.e., if and only if the PCP instance has no solution.

f) The argument is the same as (e), but let R be the regular expression (E и ly, and let L{Gi) be La U T.

□

e) IsL(Gi) Ci(G2)?

f) Is L{R) CL(Gi)?

PROOF: Each of the proofs is a reduction from PCP. We show how to take an instance {A,B) of PCP and convert it to a question about CFGs and/or regular expressions that has answer yes if and only if the instance of PCP has a solution. In some cases, we reduce PCP to the question as stated in the theorem; in other cases we reduce it to the complement. It doesnt matter, since if we show the complement of a problem to be undecidable, it is not possible that the problem itself is decidable, since the recursive languages are closed under complementation (Theorem 9.3).

We shall refer to the alphabet of the struigs for this instance as S and the alphabet of index symbols as I. Our reductions depend on the fact that La, Lb, La; and Lb all have CFGs, We construct these CFGs either directly, as in Section 9.5.2, or by the construction of a PDA for the complement languages given in Theorem 9,21 coupled with the conversion from a PDA to a CFG by Theorem 6.14,

a) Let L(Gi) = La and L{G2) - Lb. Then L{Gi) П L(G2) is the set of solutions to this instance of PCP. The intersection is empty if and only if there is no solution. Note that, technically, we have reduced PCP to the language of pairs of CFGs whose intersection is nonempty; i.e., we have shown the problem is the intersection of two CFGs nonempty to be undecidable. However, as mentioned in the introduction to the proof, showing the complement of a problem to be undecidable is tantamount to showing the problem itself undecidable.

b) Since CFGs are closed mider union, we can construct a CFG Gi for La Lb. Since (E U L)* is a regular set, we surely may construct for it a CFG G2, Now 17 и Li La П Lb- Thus, L(Gi) is missing only those strings that represent solutions to the instance of PCP. L[G2) is missing no strings in (S и /)*. Thus, their languages are equal if and only if the PCP instance has no solution.

c) The argument is the same as for (b), but we let R be the regular expression (EU/)*.

d) The argument of (c) suffices, since E U 7 is the only alphabet of which La и Lb could possibly be the closure.

! Exercise 9.5.2: Show that the language La U is a regular language if and only if it is the set of aU strings over its alphabet; i.e., if and only if the instance (A, B) of PCP has no solution. Thus, prove that it is undecidable whether or not a CFG generates a regular language. Hint: Suppose there is a solution to PCP; say the string wx is missing from La Lb, where w is a string from the alphabet S of this PCP instance, and x is the reverse of the corresponding string of index symbols. Define a homomorphism h{(3) = w and /i(l) = x. Then what is h~{LA и Ls)? Use the fact that regular sets are closed under inverse homomorphism, complementation, and the pumping lemma for regular sets to show that Ьд и Lb is not regular.

!! Exercise 9.5.3: It is undecidable whether the complement of a CFL is also a CFL. Exercise 9.5.2 can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial claim, we need to define a different language that represents the iionsolutions to an distance {A, B) of PCP. Let Lab be the set of strings of the form ttf#x#j/#z such that:

1. w and X are strings over the alphabet E of the PCP instance.

2. у and z are strings over the index alphabet / for this instance.

3. # is a symbol in neither S nor /. A wф x.

5. У5г .

6. x is not what the index string у generates according to list B.

7. w is not what the index string z generates according to the list A.

Notice that Lab consists of all strings in S*#E*#/*#L* unless the instance {A,B) has a solution, but Lab is a CFL regardless. Prove that Lab is a CFL if and only if there is no solution. Hint: Use the inverse homomorphism trick from Exercise 9.5.2 and use Ogdens lemma to force equality in the lengths of certain substrings as in the hint to Exercise 7.2.5(b).

9.5.4 Exercises for Section 9.5

Exercise 9.5.1; Let L be the set of (codes for) context-free grammars G such that L{G) contains at least one palindrome. Show that L is undecidable. Hint: Reduce PCP to L by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.