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 ${\displaystyle L}$ on säännöllinen, on olemassa ${\displaystyle p>0}$ siten, että mikä tahansa ${\displaystyle x}$, joka kuuluu kieleen ${\displaystyle L}$, missä ${\displaystyle |x|\geq p}$, voidaan kirjoittaa muotoon ${\displaystyle x=uvw}$ siten, että ${\displaystyle |uv|\leq p}$, ${\displaystyle |v|\geq 1}$ ja ${\displaystyle uv^{i}w}$ kuuluu kieleen ${\displaystyle L}$ kaikilla ${\displaystyle i}$.

Esimerkiksi kieli ${\displaystyle L=\{a^{n}b^{n}\,|\,n\geq 0\}}$ voidaan todistaa epäsäännölliseksi olettamalla, että kieli on säännöllinen, eli pumppauslemma on voimassa. Valitaan ${\displaystyle x=a^{p}b^{p}}$, jolloin ${\displaystyle |x|=2p\geq p}$, koska ${\displaystyle p>0}$, joten ${\displaystyle x}$ voidaan jakaa osiin (kun ${\displaystyle x=uvw}$), siten että ${\displaystyle |uv|\leq p}$, ${\displaystyle |v|\geq 1}$.

Valitaan ${\displaystyle u=a^{m}}$, ${\displaystyle v=a^{n}}$ ja ${\displaystyle w=a^{p-(m+n)}b^{p}}$, missä ${\displaystyle m\leq n-1}$, ${\displaystyle n\geq 1}$ ja pumpataan ${\displaystyle 0}$ kertaa, eli ${\displaystyle i=0}$. Tällöin saadaan merkkijono ${\displaystyle a^{m}a^{p-(m+n)}b^{p}=a^{p-n}b^{p}}$ ja koska ${\displaystyle n\geq 1}$, tämä merkkijono ei selvästikään kuulu kieleen ${\displaystyle L}$. Päädyttiin ristiriitaan, joten oletus oli virheellinen. Siispä kieli ${\displaystyle L}$ on saatu osoitettua epäsäännölliseksi.