Lecture 14 (Proving languages non-context free), 3/15/06

Concepts, definitions (in italics):

• Tree terms (from CSE 259): root, leaves, internal nodes, height of tree, subtree rooted at node X
• Given a CFG G and any k, there are only finitely many parse trees in G of height < k.
• Given a CFG G and any k, there exists a limit p so any string in L(G) of length >= p has a parse tree of height >= k.
• The Pumping Lemma for CFLs
• CFLs are closed under union, concatenation, star.
• CFLs are not closed under intersection, complement, or set difference.
• The intersection of a regular language and a context-free language is always context-free.

Reading:

• Chapter 2.3

Skills:

• Know new definitions, understand new concepts.
• Understand the Pumping Lemma for CFLs
• Know how to apply the Pumping Lemma for CFLs to prove that a language is not context free
• Be able to prove that if CFLs are closed under union but not under intersection, then CFLs are not closed under complement, either.
• Know how to apply the closure rules for CFLs to prove that a language is not context free

Notes:

• In the pumping lemma for CFL's, p is the limit so any string in L of length >= p has a parse tree of height >= k (where k is the number of variables in the CFG for L, in Chomsky NF).
• The pumping lemma for CFLs can show that the following languages are not context-free:
  • L₁ = {aⁿ bⁿ cⁿ: n ≥ 0}
  • L₂ = {ww: w is over {0, 1) (or any alphabet with at least two characters)}
• Proving that CFLs are not closed under intersection:
• Let L₃ =  {aⁿ bⁿ c^*: n ≥ 0} and L₄ = {a^* bⁿ cⁿ: n ≥ 0}. 
• The intersection of L₃ and L₄ is {aⁿ bⁿ cⁿ: n ≥ 0}
• Both L₃ and L₄ are context-free, but their intersection is not.
• Given a PDA M1 and a DFA M2, we can create a new "hybrid" PDA that accepts the intersection of L(M1) and L(M2), whose states are pairs of states from M1 and M2, respectively.