The Pumping Lemma for Context Free Languages

Return to List of Lectures

Previous Lecture

• Misc
  • Friday (March 4)
    • I’ll be out of town
    • “Class” will be asynchronous online discussion of history of finite automata and regular languages
    • See http://www.cs.nmsu.edu/historical-projects/Projects/kleene.9.16.10.pdf)
    • Handout Wednesday
• Questions?
• Problem Set
  • Handout
• Non-Context-Free Languages
  • Section 2.3
    • New pumping lemma for CFLs
    • If A is a CFL then there is p such that if s is string in A of length at least p then s = uvxyz such that…
      • uvⁱxyⁱz is in A for all i ≥ 0
      • |vy| > 0
      • |vxy| ≤ p
    • Proof uses parse trees and pigeonhole principle and…?
      
  • Example: aⁿb^mc^nm
    • Assume L is context free
    • Let s = a^pb^pc^{p^2}
    • Cases!
      • v & y can’t be just as and bs because pumping would violate product requirement
      • Similarly v & y can’t be only cs
      • Consider c and b being pumped (only posibility due to |vxy|≤p requirement)
        • If r bs are pumped need pr cs to be pumped
        • Violates |vxy| ≤ p requirement
      • Also, neither v nor y can contain 2 or more of a, b, c without violating order when pumped, although the previous cases by themselves are enough for the proof
• Next
  • Deterministic context free languages
  • Read section 2.4 up to but not including Theorem 2.43
    • Page 130 through first paragraph of 134

Next Lecture