Context Free, Closure

Closure

Regular languages are closed under union, intersection, substitution, etc - how about context free languages?

Given two context free grammars, let a new start symbol produce the start symbol for the first grammar or the second. The result is the union of the two languages. Thus context free languages are closed under union.

Let s generate s1s2, the start symbols for the two grammars, and the concatenation of context free languages is context free.

These languages are not closed under intersection. This is demonstrated by 0i1i2j and 0i1j2j. both are context free, but their intersection, 0j1j2j, is not.

Suppose context free languages are closed under complement. Take the intersection by finding the complement of the union of the complements. Since the intersection is not context free, we have a contradiction. This seems counterintuitive, because you can always switch the states on a pdm. doesn't this complement the language? Doesn't the pdm now accept everything it rejected before, and vice versa? It would, if the pdm was deterministic. In other words, the languages of deterministic pdms are closed under complement. But this does not hold when the pdm is nondeterministic. A judicious chain of state transitions might accept a word in the original pdm, while a different chain of transitions could accept the same word in the inverted pdm.

Note, the union of two deterministic pdms may be hopelessly nondeterministic. You just have to decide at the outset which machine you are running. You can't run both machines in parallel, because one stack may grow faster than the other, and you can't simulate that using a single stack and finite states. These languages are not closed under union or intersection. This is illustrated by the intersection of 0i1i2j and 0i1j2j, which isn't even context free. But I digress - let's get back to context free languages.

A context free language intersect a regular language is still context free. Run the npdm and fsm in parallel (merge their states), and require both machines to wind up in a final state.

Given two grammars, replace a terminal in the first grammar with the start symbol of the second. This shows context free languages are closed under substitution.

A homomorphism is a special case of substitution, where a terminal is everywhere replaced with a given word. This process is undone via an inverse homomorphism. Suppose a language is context free - if an inverse homomorphism pulls ABC back to Z, is the result context free?

Convert the grammar to greibach normal form, then to a nondeterministic pdm. Thus there are no pesky E transitions to worry about. Describe the composite transitions on the letters ABC. These will depend on the state of the machine when A is encountered, and the top three symbols on the stack. When Z is encountered, use E transitions to pop the top three symbols, and record their values using a new system of states. Then jump to a new state, and push a string of symbols, as the original machine would have done on ABC. The new machine accepts the inverse homomorphism of the language.

My notes say context free languages are closed under quotient, but I don't have a proof, so I'll just leave that one alone.