Course contentsShow
← Computer Science
Lesson 1849 of 2,87241. Context-Free LanguagesFree lesson

Pumping Lemma for Context-Free Languages

Using the pumping lemma to prove that certain languages are not context-free.

Pumping Lemma for Context-Free Languages

What you'll learn: You'll discover how to use the pumping lemma to prove that certain languages are not context-free.

The Core Idea

Just like the pumping lemma for regular languages helps identify non-regular languages, the pumping lemma for context-free languages (CFLs) is a tool for proving that certain languages cannot be generated by any context-free grammar or recognized by any pushdown automaton.

The key insight: if a language is context-free and contains sufficiently long strings, those strings must have a specific "pumpable" structure. You can identify and repeat certain substrings to generate infinitely many new strings that must also be in the language.

How It Works

When you have a long enough string in a CFL, it can be divided into five parts: uvwxy, where:

  • The middle portion (vwx) isn't too long
  • At least one of v or x is non-empty
  • You can "pump" (repeat) both v and x the same number of times: uv²wx²y, uv³wx³y, etc., and all results stay in the language

Think of it like a sandwich recipe: If your recipe is context-free, any sufficiently large sandwich must have at least one pair of repeatable layers (maybe lettuce and cheese) that you can duplicate together while keeping it a valid sandwich.

Proving Non-Context-Freeness

To prove a language is not context-free:

  1. Assume it is context-free
  2. Apply the pumping lemma to get constraints
  3. Choose a specific long string from the language
  4. Show that no matter how someone divides it into uvwxy, pumping creates a string not in the language
  5. This contradiction proves the language isn't context-free

Key Takeaway: The pumping lemma for CFLs is a proof-by-contradiction tool that reveals languages requiring more power than context-free grammars or pushdown automata can provide.