COMS W3261 CS Theory
Lecture 11: Properties of CFL's

1. Closure Properties of CFL's

• The context-free languages are closed under the following operations:
• substitution
• Let Σ be an alphabet and let L_a be a language for each symbol a in Σ. These languages define a substitution s on Σ.
• If w = a₁a₂ ... a_n is a string in Σ*, then s(w) = { x₁x₂ ... x_n | x_i is a string in s(a_i) for 1 ≤ i ≤ n }.
• If L is a language, s(L) = { s(w) | w is in L }.
• If L is a CFL over Σ and s(a) is a CFL for each a in Σ, then s(L) is a CFL.
• union
• concatenation
• Kleene star
• homomorphism
• reversal
• intersection with a regular set
• inverse homomorphism

2. Nonclosure Properties of CFL's

• The context-free languages are not closed under the following operations:
• intersection
• L₁ = { aⁿbⁿcⁱ | n, i ≥ 0 } and L₂ = { aⁱbⁿcⁿ | n, i ≥ 0 } are CFL's. But L = L₁ ∩ L₂ = { aⁿbⁿcⁿ | n ≥ 0 } is not a CFL.
• complement
• Suppose comp(L) is context free if L is context free. Since L₁ ∩ L₂ = comp(comp(L₁) ∪ comp(L₂)), this would imply the CFL's are closed under intersection.
• difference
• Suppose L₁ – L₂ is a context free if L₁ and L₂ are context free. If L is a CFL over Σ, then comp(L) = Σ* - L would be context free.

3. Testing Emptiness of a CFG

• Problem: Given a CFG G, is L(G) empty?
• Emptiness problem is decidable: determine whether the start symbol of G is generating.
• Naive algorithm has O(n²) time complexity where n is the size of G (sum of the lengths of the productions).
• With a more sophisticated list-processing algorithm, emptiness problem can be solved in linear time. See HMU, p. 302.

4. Undecidable CFL Problems

• We say a problem that cannot be solved by any Turing machine is undecidable. There is no algorithm that can solve an undecidable problem.
• We shall see that several fundamental questions about context-free grammars and languages are undecidable, such as:
1. Is a given CFG ambiguous?
2. Given a CFG, is there another equivalent CFG that is unambiguous?
3. Do two given CFG's generate the same language?
4. Is the intersection of the languages generated by two CFG's empty?
5. Given a CFG G = (V, T, P, S), is L(G) = T*?

5. Practice Problems

1. Prove the CFL's are closed under the operations in Section 1 above.
2. Let min(L) = { w | w is in L but no proper prefix of w is in L }. Are the CFL's closed under the min operation?
3. Let max(L) = { w | w is in L but for no string x other than ε is wx is in L }. Are the CFL's closed under the max operation?
4. Let init(L) = { w | wx is in L for some string x (possibly the empty string) }. Are the CFL's closed under the init operation?
5. Let cycle(L) = { w | we can write w as xy where yx is in L }. Are the CFL's closed under the cycle operation?
6. Let half(L) = { w | there exists a string x such that |w| = |x| and wx is in L }. Are the CFL's closed under the half operation?
7. Let L = { aⁿbⁿcⁿ | n ≥ 1 }. Show that the complement of L is context free.
8. Let L = { ww | w is a strings of a's and b's }. Show that the complement of L is context free.

6. Reading

• HMU: Ch. 7