Pumppauslemma

Pumppauslemma on keino osoittaa jokin formaali kieli epäsäännölliseksi. Koska kaikki säännölliset kielet ovat tunnistettavissa äärellisillä automaateilla, on kyseisten automaattien pakko sisältää jokin itseään toistava osa. Pumppauslemma perustuu tähän ajatukseen, mutta sillä ei kuitenkaan voida todistaa mitään kieltä säännölliseksi.

Pumppauslemma voidaan formalisoida seuraavasti: Jos kieli  on säännöllinen, on olemassa  siten, että mikä tahansa , joka kuuluu kieleen , missä , voidaan kirjoittaa muotoon  siten, että ,  ja  kuuluu kieleen  kaikilla .

Esimerkiksi kieli  voidaan todistaa epäsäännölliseksi olettamalla, että kieli on säännöllinen, eli pumppauslemma on voimassa. Valitaan , jolloin , koska , joten  voidaan jakaa osiin (kun ), siten että , .

Valitaan ,  ja , missä ,  ja pumpataan  kertaa, eli . Tällöin saadaan merkkijono  ja koska , tämä merkkijono ei selvästikään kuulu kieleen . Päädyttiin ristiriitaan, joten oletus oli virheellinen. Siispä kieli  on saatu osoitettua epäsäännölliseksi.

Formaalit kielet

he:למת הניפוח לשפות חופשיות הקשר