====== Pumping lemma ====== ===== Lemma ===== Nechť //L// je regulární jazyk. Pak existuje //n// ∈ **N** takové, že libovolné slovo //w ∈ L// délky alespoň //n// lze psát ve tvaru //w = xyz//, kde |//xy//| ≤ //n//, //y// ≠ //ε// a //xyⁱz ∈ L// pro každé //i// ∈ **N**₀. ===== Šablona ===== Tohle nedokazuje, že by jazyk //L// byl regulárním (to pumping lemma stejně neumí)! Jen usnadňuje důkaz že jím není. Nechť //n// je libovolné. Volíme //w// = FIXME náležící //L//, platí |//w//| ≥ //n//. Pro každé //x//, //y//, //z// náležící Σ* existuje //w// = //xyz//, |//xy//| ≤ //n//, //y// ≠ //ε// platí: * //x// = FIXME * //y// = FIXME * //z// = FIXME Pro //i// = FIXME platí: //xyⁱz// = FIXME ∉ //L// protože, FIXME. Z pumping lemmy plyne, že //L// není regulární. My volíme //w// (musí záviset na //n//) a pumpovací konstantu //i// (//i// ≠ 1). Rozdělení na //xyz// volí "nepřítel". ===== Příklad ===== //L// = {//aⁱb^ja²ⁱ// | 0 ≤ //i//, 0 ≤ //j// ≤ 5} Nechť //n// je libovolné. Volíme //w// = //aⁿb⁴a²ⁿ// náležící //L//, platí |//w//| ≥ //n//. Pro každé //x//, //y//, //z// náležící Σ* existuje //w// = //xyz//, |//xy//| ≤ //n//, //y// ≠ //ε// platí: * //x// = //a^m// * //y// = //a^n−m// * //z// = //b⁴a²ⁿ// Pro //i// = 2 platí: //xyⁱz// = //a^2n−mb⁴a²ⁿ// ∉ //L// protože, //2n − m ≠ 2n//. Obdobně to nebude platit ani pro libovolná jiná rozdělení //x//, //y//, //z//. Z pumping lemmy plyne, že //L// není regulární.