Lema de pompare

De la Wikipedia, enciclopedia liberă

În teoria limbajelor formale, o lemă de pompare spune că orice limbaj dintr-o clasă dată, dacă este "pompat", rămâne neschimbat. Pomparea unui limbaj presupune ca orice şir suficient de lung din limbaj să poată fi împărţit în componente, a căror repetare produce alte şiruri, care vor face parte toate din limbajul respectiv. Astfel, dacă există o lemă de pompare pentru o clasă dată de limbaje, majoritatea limbajelor din acea clasă va conţine o mulţime infinită de şiruri finite, toate produse prin regula simplă dată de lemă. În general, asemenea rezultate depind de principiul lui Dirichlet.

Cuprins 1 Considerente generale 2 Lema de pompare pentru limbaje regulate 2.1 Utilizare practică 2.2 Demonstraţia 2.3 Insuficienţa 3 Lema de pompare pentru limbaje independente de context 3.1 Utilizare practică 4 Bibliografie

[modifică] Considerente generale

Cele mai importante două exemple sunt lema de pompare pentru limbaje regulate şi lema de pompare pentru limbaje independente de context. Spre deosebire de teoreme, lemele sunt gândite în aşa fel încât să uşureze demonstraţiile. Aceste două leme sunt adeseori folosite pentru a determina dacă un anumit limbaj nu face parte dintr-o anumită clasă de limbaje. Totuşi, ele nu pot fi folosite pentru a determina dacă un limbaj face parte dintr-o clasă de limbaje, deoarece satisfacerea lemei de pompare este o condiţie necesară, dar nu suficientă, pentru apartenenţa la o clasă.

Ca un exemplu de aplicare practică a lemelor de pompare, cineva care cunoaşte lema de pompare pentru limbaje regulate poate vedea imediat că un limbaj care permite expresii în paranteze dar impune condiţia ca parantezele să fie echilibrate (să se închidă corect), nu poate fi un limbaj regulat, şi deci limbajul nu poate fi generat de o gramatică regulată, şi nici recunoscut de un automat finit. Încercarea de a realiza o demonstraţie a acestui fapt fără a folosi lema ar dura destul de mult.

[modifică] Lema de pompare pentru limbaje regulate

Dacă un limbaj L este regulat, atunci există un număr p > 0, reprezentând lungimea pompării, astfel încât fiecare şir w din L cu |w| ≥ p poate fi scris sub forma:

w = x y z,

cu şirurile x, y şi z respectând relaţiile |x y| ≤ p, |y| > 0 şi

x y ⁱ z face parte din L, oricare ar fi i ≥ 0.

(Observaţie: aceasta este trivial adevărată dacă limbajul nu e infinit, deoarece în acest caz p trebuie doar să fie mai mare decât lungimea celui mai lung şir din limbaj).

[modifică] Utilizare practică

Folosind această lemă, se poate demonstra de exemplu că limbajul L = {a ⁿ b ⁿ : n ≥ 0} peste alfabetul Σ = {a, b} nu este regulat. Pentru că dacă ar fi regulat, am putea alege p cu proprietatea din lema de pompare. Şirul w = a ^p b ^p face parte din L, şi lema de pompare garantează că există o descompunere w = x y z cu |x y| ≤ p, |y| ≥ 1 şi x y ⁱ z în L, pentru orice i ≥ 0. Dar atunci y trebuie să constea dintr-un număr nenul de a-uri, şi nici un b; în acest caz, x y ² z are mai multe a-uri decât b-uri şi de aceea nu este din L, contradicţie.

Demonstraţia că limbajul parantezelor echilibrate (corect închise) nu este regulat merge pe aceeaşi idee. Dat fiind p, există un şir de paranteze echilibrate care începe cu mai mult de p paranteze deschise, astfel încât y va consta doar din paranteze deschise. Repetând y, putem produce un şir care nici măcar nu mai conţine numere egale de paranteze deschise şi paranteze închise, şi deci acestea nu pot fi echilibrate.

[modifică] Demonstraţia

Ideea de demonstraţie pentru lema de pompare este următoarea: limbajul regulat este acceptat de un anumit automat finit acceptor; alegem drept p numărul stărilor acelui acceptor. Fiecare şir mai lung decât p va revizita o anumită stare a automatului, cauzând astfel o buclă ce poate fi repetată (sau nefolosită, pentru i = 0). Etichetele de-a lungul buclei corespund şirului y.

[modifică] Insuficienţa

Observaţie: Lema de pompare nu dă o condiţie suficientă ca un limbaj să fie regulat: de exemplu, limbajul { u u ^R v : u, v {0,1}⁺ } (limbajul şirurilor peste alfabetul { 0; 1 } care constau dintr-un palindrom par nevid, urmat de un alt şir nevid) nu este regulat dar tot poate fi "pompat" cu p = 4: Să considerăm un şir w = u u ^R v de lungime cel puţin 4. Dacă u are lungime 1, atunci |v| ≥ 2 şi putem lua y ca primul caracter din v. Altfel, luăm y ca fiind ultimul caracter din u, repetat, adică şirul format din cele două caractere din mijlocul şirului u u ^R, pentru care se poate observa că y ^k reprezintă şi el un palindrom, deci x y ^k z face parte din limbajul studiat. Pentru un test practic care caracterizează exact limbajele regulate, vezi teorema Myhill-Nerode.

[modifică] Lema de pompare pentru limbaje independente de context

Dacă un limbaj L este independent de context, atunci există un număr p > 0, reprezentând lungimea pompării, astfel încât orice şir w din L cu proprietatea că |w| ≥ p poate fi scris ca

w = u v x y z

unde şirurile u, v, x, y şi z au proprietăţile |v x y| ≤ p, |v y| ≥ 1 şi

u v ⁱ x y ⁱ z face parte din L pentru orice i ≥ 0.

(Pentru o generalizare a acestei leme, vezi Lema lui Ogden.)

[modifică] Utilizare practică

Lema de pompare se poate folosi pentru a arăta că anumite limbaje nu sunt independente de context. De exemplu, putem demonstra că limbajul L = { a ⁱ b ⁱ c ⁱ : i > 0 } nu este independent de context.

1. Presupunem L independent de context
   1. Condiţiile:
      1. | vxy | ≤ p. Adică porţiunea din mijloc să nu fie prea lungă.
      2. . Pentru că v şi y sunt piesele care vor fi "pompate", această condiţie impune ca cel puţin unul din şirurile de pompat să nu fie vid.
      3. Pentru orice i ≥ 0, uvⁱxyⁱz face parte din L. Adică cele două şiruri v şi y pot fi "pompate" de oricâte ori, inclusiv 0, iar şirul rezulatat va fi în continuare membru al limbajului L.
2. Dacă şirul cu | w | > p, înseamnă (conform lemei) că w = uvxyz, unde | vxy | ≤ p
3. Acum, alegem o valoare pentru o variabilă întragă i care e mai mare decât p.
4. Atunci, oricând apare uvxyz în şirul aⁱbⁱcⁱ, vxy nu poate conţine mai mult decât două litere diferite, pentru că cel mai din dreapta a este la i+1 poziţii depărtare de cel mai din stânga c.
   • De ex: Poate fi doar şir de a-uri, doar de b-uri, sau doar de c-uri, sau poate fi de a-uri şi b-uri, sau poate fi de b-uri şi c-uri.
     • Astfel, şirul vxy nu poate conţine mai mult decât două simboluri distincte, dar, conform lemei de pompare, nu poate fi nici vid, deci trebuie să conţină cel puţin un simbol.
5. Acum putem începe să "pompăm"
   1. Deoarece uvxyz face parte din L, uv²xy²z trebuie să facă şi el parte din L. Pentru că v şi y nu pot fi ambele vide, |uv²xy²z| > |uvxyz|, deci am adăugat simboluri.
   2. Dar deoarece vy nu conţine toate cele trei litere distincte, nu am avut cum să adăugăm acelaşi număr din fiecare literă. Am pompat mai multe litere şi am contrazis definiţia iniţială a lui L. Astfel, uv²xy²z nu poate fi un şir din L.
6. Am ajuns la o contradicţie. De aceea, presupunerea noastră iniţială, că L este independent de context, este falsă. q.e.d.

[modifică] Bibliografie

• Michael Sipser - "Introduction to the Theory of Computation", PWS Publishing 1997, ISBN 0-534-94728-X Secţiunea 1.4: Limbaje neregulate, pp.77–83. Secţiunea 2.3: Limbaje neindependente de context, pp.115–119.