[Verse 1] When finite states can't handle the task And regular expressions fall short at last There's languages that break the rules we know Like matching pairs that endlessly grow A to the n, B to the n, they must align But counting's not what finite states design [Chorus] Pumping lemma proves they're not regular Split the string in parts of x y z Y must pump but keeps the language pure If it breaks then non-regular we see Length of x y can't exceed the pumping bound Y can't be empty, that's the golden rule we've found [Verse 2] Take a string that's longer than pumping p Split it up where x y z agrees The middle part y pumps to any power Zero times or thousand, every hour If pumping breaks the language that we test Then regular expression fails the test [Chorus] Pumping lemma proves they're not regular Split the string in parts of x y z Y must pump but keeps the language pure If it breaks then non-regular we see Length of x y can't exceed the pumping bound Y can't be empty, that's the golden rule we've found [Bridge] Double words like w w can't be matched Balanced parentheses can't be caught Myhill Nerode shows equivalence classes Infinite means regular passes Proof by contradiction is the way Assume it's regular then watch it fray [Verse 3] Context-free grammars step up to the plate When finite automata meet their fate Push-down stacks can count and balance well What regular languages cannot tell But pumping lemma stands as gatekeeper true Dividing what finite states can do [Chorus] Pumping lemma proves they're not regular Split the string in parts of x y z Y must pump but keeps the language pure If it breaks then non-regular we see Length of x y can't exceed the pumping bound Y can't be empty, that's the golden rule we've found [Outro] When languages grow beyond finite reach Pumping lemma is the tool we teach X y z, the pattern never fails To show us where regularity pales
← 5 Closure Properties of Regular Languages | 7 Minimization of DFAs →