[Verse 1] Context-free languages have their boundaries too There's a test to prove what grammars cannot do When your string grows long, beyond the pumping length We split it into five parts to test the language strength [Chorus] U-V-X-Y-Z, that's how we slice it clean V and Y can pump together, strongest test you've ever seen V-Y cannot be empty, that would break the rule X-Y portion stays concise, that's our pumping tool Pump them up or pump them down, zero, one, or more If the language breaks apart, it's not context-free for sure [Verse 2] Take A-cubed B-cubed C-cubed, equal counts in line This pattern cannot parse with context-free design The pumping splits V-X-Y across too small a span Cannot capture all three counts with any pumping plan [Chorus] U-V-X-Y-Z, that's how we slice it clean V and Y can pump together, strongest test you've ever seen V-Y cannot be empty, that would break the rule X-Y portion stays concise, that's our pumping tool Pump them up or pump them down, zero, one, or more If the language breaks apart, it's not context-free for sure [Bridge] Double words like W-W Copies that are identical through and through Pumping cannot synchronize both halves at once Context-free grammars fail this synchronized hunt [Verse 3] Regular pumping had just one substring to repeat Context-free needs two parts to make the proof complete Parse trees grow too wide when strings exceed the bound That's where our five-piece splitting method can be found [Outro] When you need to prove a language lives beyond the wall Use the context-free pumping lemma to watch it fall
← 3 Pushdown Automata (PDA) | 5 Closure Properties of CFLs →