Det er to pumpelemmaer, som er definert for 1. Vanlige språk og 2. Kontekst – Frie språk Pumping Lemma for vanlige språk For ethvert regulært språk L finnes det et heltall n, slik at for alle x ? L med |x| ? n, det finnes u, v, w ? ?^*, slik at x = uvw, og (1) |uv| ? n (2) |v| ? 1 (3) for all i ? 0: uv^Jegw ? L Enkelt sagt betyr dette at hvis en streng v er 'pumpet', dvs. hvis v settes inn et hvilket som helst antall ganger, forblir den resulterende strengen fortsatt i L. Pumping Lemma brukes som et bevis for uregelmessighet i et språk. Derfor, hvis et språk er vanlig, tilfredsstiller det alltid pumpende lemma. Hvis det finnes minst en streng laget av pumping som ikke er i L, så er L sikkert ikke vanlig. Det motsatte av dette er kanskje ikke alltid sant. Det vil si at hvis Pumping Lemma holder, betyr det ikke at språket er regelmessig.

La oss for eksempel bevise L₀₁= n ? 0 er uregelmessig. La oss anta at L er regulær, så følger reglene ovenfor ved å pumpe Lemma. Nå, la x ? L og |x| ? n. Så, ved å pumpe Lemma, eksisterer det u, v, w slik at (1) – (3) holder. Vi viser at u, v, w, (1) – (3) ikke holder. Hvis (1) og (2) holder, er x = 0ⁿ1ⁿ= uvw med |uv| ? n og |v| ? 1. Så u = 0^en, v = 0^b, w = 0^c1ⁿhvor: a + b? n, b? 1, c? 0, a + b + c = n Men da feiler (3) for i = 0 uv⁰w = uw = 0^en0^c1ⁿ= 0^{a + c}1ⁿ? L, siden a + c ? n.

tynn algoritme

Pumping Lemma for Context-free Languages ​​(CFL) Pumping Lemma for CFL sier at for ethvert Context Free Language L er det mulig å finne to delstrenger som kan 'pumpes' et hvilket som helst antall ganger og fortsatt være på samme språk. For alle språk L deler vi strengene i fem deler og pumper andre og fjerde delstreng. Pumping Lemma, også her, brukes som et verktøy for å bevise at et språk ikke er CFL. Fordi hvis en streng ikke tilfredsstiller betingelsene, er ikke språket CFL. Således, hvis L er en CFL, eksisterer det et heltall n, slik at for alle x ? L med |x| ? n, det finnes u, v, w, x, y ? ?^*, slik at x = uvwxy, og (1) |vwx| ? n (2) |vx| ? 1 (3) for all i ? 0: uv^Jegwx^Jegog ? l

gjennomstrekning

For eksempel ovenfor, 0ⁿ1ⁿer CFL, ettersom en hvilken som helst streng kan være et resultat av å pumpe to steder, en for 0 og en annen for 1. La oss bevise, L₀₁₂= n ? 0 er ikke kontekstfri. La oss anta at L er kontekstfri, så ved Pumping Lemma følger reglene ovenfor. Nå, la x ? L og |x| ? n. Så ved å pumpe Lemma eksisterer det u, v, w, x, y slik at (1) – (3) holder. Vi viser at for alle u, v, w, x, y (1) – (3) ikke holder. Hvis (1) og (2) holder, er x = 0ⁿ1ⁿ2ⁿ= uvwxy med |vwx| ? n og |vx| ? 1. (1) forteller oss at vwx ikke inneholder både 0 og 2. Dermed har enten vwx ingen 0-er, eller vwx har ingen 2-er. Vi har derfor to saker å vurdere. Anta at vwx ikke har noen 0-er. Ved (2), inneholder vx en 1 eller en 2. Dermed har uwy 'n' 0'er og uwy har enten mindre enn 'n' 1'er eller har mindre enn 'n' 2'er. Men (3) forteller oss at uwy = uv⁰wx⁰y ? L. Så, uwy har et likt antall 0-er, 1-er og 2-er gir oss en selvmotsigelse. Tilfellet der vwx ikke har noen 2-er er likt og gir oss også en selvmotsigelse. Dermed er ikke L kontekstfri. Kilde : John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Introduksjon til automatteori, språk og beregning.

Denne artikkelen er bidratt av Nirupam Singh .