Lema de creștere

Lema de pompare ( lema de creștere , lema de pompare ; lema de pompare în engleză ) este o afirmație importantă a teoriei automatelor , permițând în multe cazuri să se verifice dacă un anumit limbaj este automat . Deoarece toate limbile finite sunt automate, este logic să faceți această verificare numai pentru limbi infinite. Termenul „pompare” din titlul lemei reflectă posibilitatea repetării repetate a unui subșir în orice șir de lungime adecvată în orice limbaj de automată infinită.

Există, de asemenea, o lemă de creștere pentru limbile fără context , o declarație și mai generală este lema de creștere pentru limbile indexate .

Formulare

Pentru un limbaj automat infinit peste un alfabet , există un număr natural , astfel încât pentru orice cuvânt de lungime cel puțin există cuvinte astfel încât , și pentru fiecare număr întreg nenegativ șirul este un cuvânt al limbii . $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$

Notarea în cuantificatori:

(\există n\in \mathbb {N} )(\forall \alpha \in L:|\alpha |\geqslant n)(\există 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\ in EU)]

Dovada

Fie ca un limbaj automat să conțină un număr infinit de lanțuri și să presupunem că este recunoscut de un automat finit determinist cu stări . Pentru a verifica concluzia lemei, alegem un lanț arbitrar al acestui limbaj care are lungimea . $L$ $L$ $A$ $n$ $\alfa$ $n$

Dacă automatul finit recunoaște , atunci lanțul este permis de acest automat, adică în automat există o cale de lungime de la starea inițială la una dintre stările finale, marcată cu simboluri de lanț . Această cale nu poate fi simplă, trebuie să treacă exact prin stare, în timp ce automatul are stări. Aceasta înseamnă că această cale trece de cel puțin două ori prin aceeași stare a automatului , adică există un ciclu cu o stare care se repetă pe această cale. Să fie aceasta o stare care se repetă . $A$ $L$ $\alfa$ $A$ $n$ $\alfa$ $n+1$ $A$ $n$ $A$ $q_{k}$

Să împărțim lanțul în trei părți, astfel încât , unde este sublanțul care se transferă de la stat înapoi la stat și este sublanțul care se transferă de la stare la starea finală. Rețineți că ambele și pot fi goale, dar subșirul nu poate fi gol. Dar atunci este evident că automatul trebuie să permită și lanțul , deoarece subșirul repetat urmează din nou calea ciclică de la la , precum și lanțul și oricare dintre forme . $\alfa$ $\alpha=uvw$ $v$ $A$ $q_{k}$ $q_{k}$ $w$ $A$ $q_{k}$ $u$ $w$ $v$ $A$ $uvvw$ $v$ $q_{k}$ $q_{k}$ $uvvvv$ $uvv...vw$

Acest raționament constituie dovada lemei de pompare.

Formulare inversă

O altă formă a acestei leme, care uneori este mai convenabil de aplicat pentru a demonstra că o anumită limbă nu este automată, pentru o limbă peste un alfabet este următoarea - dacă cazul este valabil: $L$ $V$

(\forall n\in \mathbb {N} )(\există \alpha \in 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 \ in EU

atunci limbajul este neautomat. $L$

Pentru a demonstra că o limbă nu este automată, se poate folosi și faptul că intersecția limbilor obișnuite este regulată. Astfel, este problematică aplicarea directă a lemei de pompare la limbajul structurilor regulate de paranteze din alfabet , dar intersecția sa cu limbajul dă limbajul , a cărui non-automaticitate rezultă trivial din lema de pompare. $\{(,)\}$ $(^{*})^{*}$ $(^{n})^{n}$

Literatură

John Hopcroft , Rajiv Motwani , Jeffrey Ullman . Introducere în teoria automatelor, limbaje și calcul. - M .: „Williams” , 2002. - S. 528. - ISBN 0-201-44124-1 .

Link -uri

Limbi și gramatici formale
Pentus, A. E., Pentus, M. R. Teoria limbajelor formale. Ghid de studiu . M., 2004
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoria și implementarea limbajelor de programare - M.: MZ-Press, 2006, ed. a 2-a. — ISBN 5-94073-094-9
Vinokurov N.S. Complexitatea unor probleme naturale în structurile automate // Sib. matematica. revista, 2005, Volumul 46, Nr. 1. (link inaccesibil din 13.05.2013 [3456 zile] - istoric )