Pumppauslemma

Kohteesta Wikipedia
Loikkaa: valikkoon, hakuun

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.

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