Kasvu Lemma

Pumppauslemma ( kasvulemma , pumppauslemma ; englanniksi pumping lemma ) on tärkeä automaatioteorian väite , jonka avulla voidaan monissa tapauksissa tarkistaa, onko tietty kieli automaatti . Koska kaikki äärelliset kielet ovat automaattisia, on järkevää tehdä tämä tarkistus vain äärettömille kielille. Termi "pumppaus" lemman otsikossa heijastaa mahdollisuutta toistua jokin osamerkkijono missä tahansa sopivanpituisessa merkkijonossa millä tahansa äärettömällä automaattikielellä.

Kontekstivapaille kielille on olemassa myös kasvulemma , vielä yleisempi lausunto on kasvulemma hakemistokielille .

Sanamuoto

Äärettömälle automaatikaelelle aakkosten yli on olemassa luonnollinen luku , niin että millä tahansa pituisella sanalla on ainakin sellaisia sanoja , että , ja jokaiselle ei-negatiiviselle kokonaisluvulle merkkijono on kielen sana . $L$ $V$ $n$ $\alpha \in L$ $n$ $u,v,w\in V^{*}$ $\alpha =uvw$ $|uv|\leqslant n$ $|v|\geqslant 1$ $i$ $uv^{i}w$ $L$

Merkintä kvantaattoreissa:

(\exists n\in \mathbb {N} )(\forall \alpha \in L:|\alpha |\geqslant n)(\exists u,v,w\in V^{*}):\ ,[\alpha =uvw\land |uv|\leqslant n\land |v|\geqslant 1\land (\forall i\in \mathbb {N} \cup \{0\},uv^{i}w\ L)]

Todiste

Olkoon automaattikieli sisältää äärettömän määrän ketjuja ja oletetaan, että sen tunnistaa deterministinen äärellinen automaati , jossa on tila . Lemman päätelmän tarkistamiseksi valitsemme mielivaltaisen tämän kielen ketjun, jonka pituus on . $L$ $L$ $A$ $n$ $\alpha$ $n$

Jos äärellinen automaatti tunnistaa , niin tämä automaatti sallii ketjun , eli automaatissa on pituinen polku alkutilasta johonkin lopputilasta, merkitty ketjusymboleilla . Tämä polku ei voi olla yksinkertainen, sen täytyy kulkea tarkalleen tilan läpi, kun taas automaatilla on tiloja. Tämä tarkoittaa, että tämä polku kulkee vähintään kahdesti saman automaatin tilan läpi, eli tällä polulla on sykli, jossa on toistuva tila. Olkoon tämä toistuva tila . $A$ $L$ $\alpha$ $A$ $n$ $\alpha$ $n+1$ $A$ $n$ $A$ $q_{k}$

Jaetaan ketju kolmeen osaan, niin että , missä on tilasta takaisin tilaan siirtyvä osaketju ja tilasta lopputilaan siirtyvä osaketju . Huomaa, että molemmat ja voivat olla tyhjiä, mutta alimerkkijono ei voi olla tyhjä. Mutta sitten on selvää, että automaatin on myös sallittava ketju , koska toistuva osamerkkijono seuraa taas syklistä polkua kohteesta kohteeseen , samoin kuin ketjua ja mitä tahansa muotoa . $\alpha$ $\alpha=uvw$ $v$ $A$ $q_{k}$ $q_{k}$ $w$ $A$ $q_{k}$ $u$ $w$ $v$ $A$ $uvvw$ $v$ $q_{k}$ $q_{k}$ $uvvvw$ $uvv...vw$

Tämä päättely on todiste pumppauslemmasta.

Käänteinen sanamuoto

Toinen tämän lemman muoto, jota on joskus helpompi soveltaa todistamaan, että tietty kieli on ei-automaattinen, sillä aakkosten yli oleva kieli on seuraava - jos tapaus pitää paikkansa: $L$ $V$

(\forall n\in \mathbb {N} )(\exists \alpha \in L\colon |\alpha |\geqslant n)(\forall u,v,w\in V^{*}\colon \alpha =uvw\land |v|\geqslant 1\ \land |uv|\leqslant n)(\olemassa i\in \mathbb {N} \cup \{0\})uv^{i}w\not \ in L

silloin kieli ei ole automaattinen. $L$

Todistamaan, että kieli ei ole automaattinen, voidaan käyttää myös sitä tosiasiaa, että säännöllisten kielten leikkauspiste on säännöllinen. On siis ongelmallista soveltaa pumppauslemmaa suoraan aakkosten säännöllisten hakasulkurakenteiden kieleen , mutta sen leikkaus kielen kanssa antaa kielen , jonka epäautomaatisuus seuraa triviaalisti pumppauslemmasta. $\{(,)\}$ $(^{*})^{*}$ $(^{n})^{n}$

Kirjallisuus

John Hopcroft , Rajiv Motwani , Jeffrey Ullman . Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .

Linkit

Muodolliset kielet ja kieliopit
Pentus, A. E., Pentus, M. R. Formaalisten kielten teoria. Opinto-opas . M., 2004
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Ohjelmointikielten teoria ja toteutus - M.: MZ-Press, 2006, 2. painos. — ISBN 5-94073-094-9
Vinokurov N.S. Joidenkin luonnollisten ongelmien monimutkaisuus automaatirakenteissa // Sib. matematiikka. aikakauslehti, 2005, osa 46, nro 1. (pääsemätön linkki 13.5.2013 [3456 päivää] - historia )