Existujú dve Pumping Lemmy, ktoré sú definované pre 1. Regulárne jazyky a 2. Kontext – Voľné jazyky Pumping Lemma pre regulárne jazyky Pre každý regulárny jazyk L existuje celé číslo n, takže pre všetky x ? L s |x| ? n, existuje u, v, w ? ?*, takže x = uvw a (1) |uv| ? n (2) |v| ? 1 (3) pre všetky i ? 0: UViw ? L Zjednodušene to znamená, že ak je reťazec v „pumpovaný“, t. j. ak je v vložené ľubovoľne veľakrát, výsledný reťazec stále zostáva v L. Pumping Lemma sa používa ako dôkaz nepravidelnosti jazyka. Ak je teda jazyk regulárny, vždy spĺňa pumpovaciu lemu. Ak existuje aspoň jedna struna vyrobená pumpovaním, ktorá nie je v L, potom L určite nie je pravidelné. Opak toho nemusí byť vždy pravdou. To znamená, že ak platí Pumping Lemma, neznamená to, že jazyk je regulárny.
Dokážme napríklad L01= n? 0 je nepravidelná. Predpokladajme, že L je regulárne, potom pri Pumping Lemma platia vyššie uvedené pravidlá. Teraz nech x ? L a |x| ? n. Takže podľa Pumping Lemma existuje u, v, w také, že platí (1) – (3). Ukazujeme, že pre všetky u, v, w, (1) – (3) neplatí. Ak platia (1) a (2), potom x = 0n1n= uvw s |uv| ? n a |v| ? 1. Takže u = 0a, v = 0bw = 0c1nkde: a + b? n, b? 1, c? 0, a + b + c = n Ale potom (3) zlyhá pre i = 0 uv0w = uw = 0a0c1n= 0a + c1n? L, pretože a + c ? n.
Pumping Lemma pre bezkontextové jazyky (CFL) Pumping Lemma pre CFL uvádza, že pre akýkoľvek bezkontextový jazyk L je možné nájsť dva podreťazce, ktoré možno „pumpovať“ ľubovoľne veľakrát a stále sú v rovnakom jazyku. Pre akýkoľvek jazyk L rozdelíme jeho reťazce na päť častí a pumpujeme druhý a štvrtý podreťazec. Pumping Lemma sa tu tiež používa ako nástroj na preukázanie, že jazyk nie je CFL. Pretože, ak niektorý reťazec nespĺňa svoje podmienky, potom jazyk nie je CFL. Ak teda L je CFL, existuje celé číslo n, takže pre všetky x ? L s |x| ? n, existuje u, v, w, x, y ? ?*, takže x = uvwxy a (1) |vwx| ? n (2) |vx| ? 1 (3) pre všetky i ? 0: UViwxia ? l
Pre vyššie uvedený príklad 0n1nje CFL, pretože každá struna môže byť výsledkom pumpovania na dvoch miestach, jedno pre 0 a druhé pre 1. Ukážme, L012= n? 0 nie je bez kontextu. Predpokladajme, že L je bezkontextové, potom podľa Pumping Lemma platia vyššie uvedené pravidlá. Teraz nech x ? L a |x| ? n. Takže podľa Pumping Lemma existuje u, v, w, x, y tak, že platí (1) – (3). Ukážeme, že pre všetky u, v, w, x, y (1) – (3) neplatia. Ak platia (1) a (2), potom x = 0n1n2n= uvwxy s |vwx| ? n a |vx| ? 1. (1) nám hovorí, že vwx neobsahuje 0 aj 2. Teda buď vwx nemá žiadne 0, alebo vwx nemá žiadne 2. Preto musíme zvážiť dva prípady. Predpokladajme, že vwx nemá žiadne 0. Podľa (2) vx obsahuje 1 alebo 2. Teda uwy má „n“ 0 a uwy má buď menej ako „n“ 1, alebo má menej ako „n“ 2. Ale (3) nám hovorí, že uwy = uv0wx0y ? L. Takže uwy má rovnaký počet 0, 1 a 2, čo nám dáva rozpor. Prípad, keď vwx nemá žiadne 2, je podobný a tiež nám dáva rozpor. L teda nie je bezkontextové. Zdroj: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Úvod do teórie automatov, jazykov a výpočtov.
java dedičnosť
K tomuto článku prispel používateľ Nirupam Singh .