Tillväxt Lemma

Det pumpande lemma ( tillväxtlemma , pumpande lemma ; engelska pumping lemma ) är ett viktigt påstående inom automatteorin , som i många fall tillåter att kontrollera om ett givet språk är automatiserat . Eftersom alla finita språk är automater, är det vettigt att göra denna kontroll endast för oändliga språk. Termen "pumpning" i rubriken på lemma reflekterar möjligheten till upprepad upprepning av någon delsträng i valfri sträng av lämplig längd i vilket oändligt automatspråk som helst.

Det finns också ett tillväxtlemma för sammanhangsfria språk , ett ännu mer allmänt påstående är tillväxtlemmat för indexspråk .

Formulering

För ett oändligt automatspråk över ett alfabet , finns det ett naturligt tal , så att det för alla ord av längd åtminstone finns ord sådana att , , och för varje icke-negativt heltal är strängen ett ord i språket . $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$

Notation i kvantifierare:

(\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\ i L)]

Bevis

Låt ett automatspråk innehålla ett oändligt antal kedjor och antag att det känns igen av en deterministisk finit automat med tillstånd . För att kontrollera slutsatsen av lemma väljer vi en godtycklig kedja av detta språk som har längd . $L$ $L$ $A$ $n$ $\alfa$ $n$

Om den finita automaten känner igen , är kedjan tillåten av denna automat, det vill säga i automaten finns en längdväg från initial till ett av sluttillstånden, markerad med kedjesymboler . Denna väg kan inte vara enkel, den måste passera exakt genom tillståndet, medan automaten har tillstånd. Detta betyder att denna väg passerar minst två gånger genom samma tillstånd av automaten , det vill säga det finns en cykel med ett upprepat tillstånd på denna väg. Låt detta vara ett upprepande tillstånd . $A$ $L$ $\alfa$ $A$ $n$ $\alfa$ $n+1$ $A$ $n$ $A$ $q_{k}$

Låt oss dela upp kedjan i tre delar, så att , var är underkedjan som överförs från staten tillbaka till staten , och är underkedjan som överförs från staten till det slutliga tillståndet. Observera att både och kan vara tomma, men delsträngen kan inte vara tom. Men då är det uppenbart att automaten också måste tillåta kedjan , eftersom den upprepade delsträngen återigen följer den cykliska vägen från till , såväl som kedjan och någon av formen . $\alfa$ $\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$

Detta resonemang utgör beviset på det pumpande lemmat.

Omvänd formulering

En annan form av detta lemma, som ibland är bekvämare att tillämpa för att bevisa att ett visst språk är icke-automatiskt, för ett språk över ett alfabet är följande - om fallet gäller: $L$ $V$

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

då är språket icke-automatiskt. $L$

För att bevisa att ett språk är icke-automatiskt kan man också använda det faktum att skärningspunkten mellan vanliga språk är regelbunden. Det är alltså problematiskt att direkt applicera det pumpande lemmat på språket för vanliga parentesstrukturer i alfabetet , men dess skärning med språket ger språket , vars icke-automatik trivialt följer av det pumpande lemmat. $\{(,)\}$ $(^{*})^{*}$ $(^{n})^{n}$

Litteratur

John Hopcroft , Rajiv Motwani , Jeffrey Ullman . Introduktion till automatteori, språk och beräkningar. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .

Länkar

Formella språk och grammatik
Pentus, A. E., Pentus, M. R. Teori om formella språk. Studiehandledning . M., 2004
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori och implementering av programmeringsspråk - M.: MZ-Press, 2006, 2nd ed. — ISBN 5-94073-094-9
Vinokurov N.S. Komplexiteten hos vissa naturliga problem i automatkonstruktioner // Sib. matematik. magazine, 2005, volym 46, nr 1. (otillgänglig länk från 2013-05-13 [3456 dagar] - historia )