Istnieją dwa lematy o pompowaniu, które są zdefiniowane dla 1. Języków regularnych i 2. Kontekstu – języków wolnych Lemat o pompowaniu dla języków regularnych Dla dowolnego języka regularnego L istnieje liczba całkowita n taka, że ​​dla każdego x ? L z |x| ? n, istnieje u, v, w? ? ^* , takie, że x = uvw i (1) |uv| ? n (2) |v| ? 1 (3) dla wszystkich? 0: UV ^I w? L Mówiąc najprościej, oznacza to, że jeśli ciąg v zostanie „pompowany”, tj. jeśli v zostanie wstawiony dowolną liczbę razy, wynikowy ciąg nadal pozostanie w L. Lemat o pompowaniu używany jest jako dowód na nieprawidłowość języka. Zatem jeśli język jest regularny, zawsze spełnia lemat o pompowaniu. Jeśli istnieje przynajmniej jedna struna powstała w wyniku pompowania, która nie znajduje się w L, to L z pewnością nie jest regularne. Nie zawsze może być odwrotnie. Oznacza to, że jeśli Lemat o pompowaniu jest prawdziwy, nie oznacza to, że język jest regularny.

Udowodnijmy na przykład, że L ₀₁ = n? 0 jest nieregularne. Załóżmy, że L jest regularne, a następnie stosując Lemat o Pompowaniu, podążamy za podanymi powyżej regułami. A teraz niech x? L i |x| ? N. Zatem, zgodnie z lematem o pompowaniu, istnieje u, v, w takie, że (1) – (3) zachodzi. Pokazujemy, że dla wszystkich u, v, w, (1) – (3) nie zachodzi. Jeśli (1) i (2) zachodzą, to x = 0 ^N 1 ^N = uvw z |uv| ? n i |v| ? 1. Zatem u = 0 ^A , v = 0 ^B , w = 0 ^C 1 ^N gdzie: a + b? n, b? 1, c? 0, a + b + c = n Ale wtedy (3) nie sprawdza się dla i = 0 uv ⁰ w = uw = 0 ^A 0 ^C 1 ^N = 0 ^{a + c} 1 ^N ? L, ponieważ a + c? N.

Lemat o pompowaniu dla języków bezkontekstowych (CFL) Lemat o pompowaniu dla CFL stwierdza, że ​​dla dowolnego języka bezkontekstowego L możliwe jest znalezienie dwóch podciągów, które można „pompować” dowolną liczbę razy i nadal być w tym samym języku. Dla dowolnego języka L dzielimy jego ciągi na pięć części i pompujemy drugi i czwarty podciąg. Lemat o pompowaniu również tutaj jest używany jako narzędzie do udowodnienia, że ​​język nie jest CFL. Ponieważ jeśli jakikolwiek ciąg znaków nie spełnia swoich warunków, wówczas językiem nie jest CFL. Zatem, jeśli L jest świetlówką CFL, istnieje liczba całkowita n taka, że ​​dla wszystkich x ? L z |x| ? n, istnieje u, v, w, x, y? ? ^* , tak że x = uvwxy i (1) |vwx| ? n (2) |vx| ? 1 (3) dla wszystkich? 0: UV ^I wx ^I I ? l

Dla powyższego przykładu 0 ^N 1 ^N to CFL, ponieważ dowolny ciąg może być wynikiem pompowania w dwóch miejscach, jednym dla 0, a drugim dla 1. Udowodnimy, L ₀₁₂ = n? 0 nie jest bezkontekstowe. Załóżmy, że L jest bezkontekstowe, a następnie stosując lemat o pompowaniu, zastosujemy się do podanych powyżej zasad. A teraz niech x? L i |x| ? N. Zatem, zgodnie z lematem o pompowaniu, istnieje u, v, w, x, y takie, że (1) – (3) zachodzi. Pokazujemy, że dla wszystkich u, v, w, x, y (1) – (3) nie zachodzi. Jeśli (1) i (2) zachodzą, to x = 0 ^N 1 ^N 2 ^N = uvwxy z |vwx| ? n i |vx| ? 1. (1) mówi nam, że vwx nie zawiera zarówno 0, jak i 2. Zatem albo vwx nie ma zer, albo vwx nie ma dwójek. Mamy więc dwa przypadki do rozważenia. Załóżmy, że vwx nie ma zer. Zgodnie z (2) vx zawiera 1 lub 2. Zatem uwy ma „n” 0, a uwy albo ma mniej niż „n” 1, albo ma mniej niż „n” 2. Ale (3) mówi nam, że uwy = uv ⁰ wx ⁰ ty? L. Zatem uwy ma taką samą liczbę zer, jedynek i dwójek, co daje nam sprzeczność. Przypadek, w którym vwx nie ma dwójek, jest podobny i również daje nam sprzeczność. Zatem L nie jest bezkontekstowe. Źródło: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Wprowadzenie do teorii automatów, języków i obliczeń.

Ten artykuł został napisany przez Nirupama Singha .