Recall that the regular languages are closed under the following set operations:

• union (if X, Y regular then X È Y is regular)
• product (if X, Y regular then XY is regular)
• Kleene closure (if X is regular then X * is regular)
• intersection (if X, Y regular then X Ç Y is regular)
• complementation (if X is regular then X¢ is regular)

Proof by grammar, by example

Language X’s grammar: S ® Ba | Bc, B ® b
Language Y’s grammar: S ® BaC, B ® b, C ® c

Rename the nonterminals so that there is no overlap:

X: S₁ ® Ba | Bc, B ® b
Y: S₂ ® DaC, D ® b, C ® c

S ® S₁ | S₂
S₁ ® Ba | Bc, B ® b
S₂ ® DaC, D ® b, C ® c

Language X’s machine:	Language Y’s machine:
(the rest of the machine)	(the rest of the machine)

Replace any accepting state:

proof by grammar, by example

Language X’s grammar: S ® Ba | Bc, B ® b
Language Y’s grammar: S ® BaC, B ® b, C ® c

Rename the nonterminals so that there is no overlap

X: S₁ ® Ba | Bc, B ® b
Y: S₂ ® DaC, D ® b, C ® c

S ® S₁S₂
S₁ ® Ba | Bc, B ® b
S₂ ® DaC, D ® b, C ® c

Call the machines for X and Y, MX and MY, resp..

1. alter MX so that it will enter an accepting state according to the above Lemma.

2.

if MX has accepting state:	and MY has start state:

 "wire" them together like so, thus "passing by" MX’s accepting state and MY’s start state:

Remember, a PDA can accept a string before it has been completely read. If, for instance, MX accepts the string "aaabcdef" after it sees the b, and MY accepts a "ggg", we still need to be able to accept "aaabcdefggg". But since we have modified MX according to the Lemma, it will also accept after reading the c, and after reading the d, etc., so that along one path it will consume the rest of the string "aaabcdef" before going on to recognize (via MY’s part of the combined machine) the ggg.

proof by grammar, by example

Language X’s grammar: S ® Ba | Bc, B ® b

Rename X’s sentence symbol: S₁ ® Ba | Bc, B ® b

Add two new productions to form X*’s grammar:

The proof is by counter-example.

L₁ = aⁿbⁿc^m (equal numbers of a’s and b’s, followed by arbitrary many c’s).
                    L₁ = (aⁿbⁿ)(cⁿ), the product of two CFL’s, hence is CF.
L₂ = a^mbⁿcⁿ (arbitrary many a’s, followed by equal numbers of c’s and d’s). Likewise CF.

Now think about L₃ = L₁ Ç L₂. Any string of L₃ must have #a’s = #b’s and #b’s = # c’s. That is,
L_{3 =} aⁿbⁿcⁿ, which we know not to be a CFL.

Of course, some intersections of CFL’s are CF:
If L₁ = PALINDROME, and L₂ = a⁺b⁺a⁺, then L₁ Ç L₂ = aⁿb^mcⁿ, which is easily seen to be CF.

(proof by contradiction)

Assume the CFL’s are closed under complementation. Then if L₁and L₂ are CFL, then so are

1. L₁^¢ and L₂^¢ (by assumption)
2. L₁^¢ È L₂^¢ (CFL’s are closed under È )
3. (L₁^¢ È L₂^¢ )^¢ (again, by assumption)

But the last is (by DeMorgan’s law) just L₁ Ç L₂. But the CFL's are not closed under Ç. Contradiction, so the assumption must be false, and the theorem true.

Again, some complements of CFL’s are CF.

(proof by machine)

The deterministic CFL’s are those that can be accepted by a deterministic PDA. For such a PDA, we can simply change each ACCEPT state to a REJECT state, and vice-versa. The new machine will accept the complement of the language of the old machine.

This trick will not work for a non-deterministic machine. Suppose an input leads to both ACCEPT and REJECT states. By definition, it will be accepted.  Use the above trick to create a machine to reject the input. That input will still terminate in an ACCEPT and a REJECT state, and the string will still be accepted.

If it could, then its complement would also be a CFL, contrary to the theorem that the CFL’s are not closed under complementation.

(see proof in book)