Există două leme de pompare, care sunt definite pentru 1. Limbi obișnuite și 2. Context – Limbi libere Lema de pompare pentru limbaje obișnuite Pentru orice limbaj regulat L, există un întreg n, astfel încât pentru toate x ? L cu |x| ? n, există u, v, w? ?^*, astfel încât x = uvw și (1) |uv| ? n (2) |v| ? 1 (3) pentru toate i ? 0: UVⁱw ? L În termeni simpli, aceasta înseamnă că dacă un șir v este „pompat”, adică dacă v este inserat de orice număr de ori, șirul rezultat rămâne în continuare în L. Lema de pompare este folosită ca o dovadă a neregularității unui limbaj. Astfel, dacă o limbă este obișnuită, întotdeauna satisface lema de pompare. Dacă există cel puțin un șir făcut din pompare care nu este în L, atunci L nu este cu siguranță obișnuit. Opusul acestui lucru poate să nu fie întotdeauna adevărat. Adică, dacă Pumping Lema este valabilă, nu înseamnă că limbajul este obișnuit.

De exemplu, să demonstrăm L₀₁= n ? 0 este neregulat. Să presupunem că L este regulat, apoi prin Lema de pompare urmează regulile date de mai sus. Acum, fie x ? L și |x| ? n. Deci, prin Lema de pompare, există u, v, w astfel încât (1) – (3) să fie valabile. Arătăm că pentru toate u, v, w, (1) – (3) nu este valabilă. Dacă (1) și (2) sunt valabile, atunci x = 0ⁿ1ⁿ= uvw cu |uv| ? n și |v| ? 1. Deci, u = 0^A, v = 0^b, w = 0^c1ⁿunde: a + b? n, b? 1,c? 0, a + b + c = n Dar, atunci (3) eșuează pentru i = 0 uv⁰w = uw = 0^A0^c1ⁿ= 0^{a + c}1ⁿ? L, deoarece a + c ? n.

Pumping Lema pentru limbaje fără context (CFL) Lema de pompare pentru CFL afirmă că, pentru orice limbaj fără context L, este posibil să găsiți două subșiruri care pot fi „pompate” de orice număr de ori și să fie încă în aceeași limbă. Pentru orice limbaj L, îi împărțim șirurile în cinci părți și pompăm al doilea și al patrulea subșir. Pumping Lema, și aici, este folosită ca instrument pentru a demonstra că o limbă nu este CFL. Pentru că, dacă vreun șir nu își îndeplinește condițiile, atunci limbajul nu este CFL. Astfel, dacă L este un CFL, există un număr întreg n, astfel încât pentru toate x ? L cu |x| ? n, există u, v, w, x, y? ?^*, astfel încât x = uvwxy și (1) |vwx| ? n (2) |vx| ? 1 (3) pentru toate i ? 0: UVⁱwxⁱși ? l

Pentru exemplul de mai sus, 0ⁿ1ⁿeste CFL, deoarece orice șir poate fi rezultatul pompării în două locuri, unul pentru 0 și altul pentru 1. Să demonstrăm, L₀₁₂= n ? 0 nu este fără context. Să presupunem că L este fără context, apoi prin Lema de pompare urmează regulile date de mai sus. Acum, fie x ? L și |x| ? n. Deci, prin lema de pompare, există u, v, w, x, y astfel încât (1) – (3) să fie valabile. Arătăm că pentru toate u, v, w, x, y (1) – (3) nu sunt valabile. Dacă (1) și (2) sunt valabile, atunci x = 0ⁿ1ⁿ2ⁿ= uvwxy cu |vwx| ? n și |vx| ? 1. (1) ne spune că vwx nu conține atât 0, cât și 2. Astfel, fie vwx nu are 0, fie vwx nu are 2. Astfel, avem două cazuri de luat în considerare. Să presupunem că vwx nu are zerouri. Prin (2), vx conține un 1 sau un 2. Astfel uwy are „n” 0 și uwy fie are mai puțin de „n” 1, fie are mai puțin de „n” 2. Dar (3) ne spune că uwy = uv⁰wx⁰y? L. Deci, uwy are un număr egal de 0, 1 și 2 ne dă o contradicție. Cazul în care vwx nu are 2 este similar și, de asemenea, ne oferă o contradicție. Astfel, L nu este lipsit de context. Sursa: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Introducere în teoria automatelor, limbaje și calcul.

Acest articol a fost contribuit de Nirupam Singh .

java priorityqueue