Pumppauslemma

Wikipedia

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 ideaan, mutta sillä ei kuitenkaan voida todistaa mitään kieltä säännölliseksi.

Pumppauslemma voidaan formalisoida seuraavasti: Jos kieli L on säännöllinen, on olemassa p > 0 siten, että mikä tahansa x, joka kuuluu kieleen L, missä , voidaan kirjoittaa muotoon x = uvw siten, että , ja uvⁱw kuuluu kieleen L kaikilla i.

Esimerkiksi kieli voidaan todistaa epäsäännölliseksi olettamalla, että kieli on säännöllinen, eli pumppauslemma on voimassa. Valitaan x = a^pb^p, jolloin , koska p > 0, joten x voidaan jakaa osiin (kun x = uvw), siten että , .

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

Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.