Det finns två pumplemma, som definieras för 1. Vanliga språk och 2. Kontext – fria språk Pumpande Lemma för vanliga språk För alla reguljära språk L finns det ett heltal n, så att för alla x ? L med |x| ? n, det finns u, v, w ? ?^*, så att x = uvw, och (1) |uv| ? n (2) |v| ? 1 (3) för all i ? 0: uvⁱw ? L Enkelt uttryckt betyder detta att om en sträng v är 'pumpad', d.v.s. om v infogas hur många gånger som helst, så förblir den resulterande strängen fortfarande i L. Pumping Lemma används som ett bevis för oegentligheter i ett språk. Således, om ett språk är regelbundet, tillfredsställer det alltid pumpande lemma. Om det finns minst en sträng gjord från pumpning som inte är i L, så är L säkert inte regelbunden. Motsatsen till detta är kanske inte alltid sant. Det vill säga om Pumping Lemma håller betyder det inte att språket är regelbundet.

Låt oss till exempel bevisa L₀₁= n ? 0 är oregelbundet. Låt oss anta att L är regelbundet, sedan följer ovanstående regler genom att pumpa Lemma. Låt nu x? L och |x| ? n. Så, genom att pumpa Lemma, finns det u, v, w så att (1) – (3) håller. Vi visar att u, v, w, (1) – (3) inte håller. Om (1) och (2) håller är x = 0ⁿ1ⁿ= uvw med |uv| ? n och |v| ? 1. Så, u = 0^a, v = 0^b, w = 0^c1ⁿvar: a + b? n, b? 1, c? 0, a + b + c = n Men då misslyckas (3) för i = 0 uv⁰w = uw = 0^a0^c1ⁿ= 0^{a + c}1ⁿ? L, eftersom a + c ? n.

Pumping Lemma for Context-free Languages ​​(CFL) Pumping Lemma för CFL säger att för alla Context Free Language L är det möjligt att hitta två delsträngar som kan 'pumpas' hur många gånger som helst och fortfarande vara på samma språk. För alla språk L delar vi upp dess strängar i fem delar och pumpar andra och fjärde delsträngar. Pumping Lemma, även här, används som ett verktyg för att bevisa att ett språk inte är CFL. För om någon sträng inte uppfyller sina villkor är språket inte CFL. Således, om L är en CFL, finns det ett heltal n, så att för alla x ? L med |x| ? n, det finns u, v, w, x, y ? ?^*, så att x = uvwxy, och (1) |vwx| ? n (2) |vx| ? 1 (3) för all i ? 0: uvⁱwxⁱoch ? l

Till exempel ovan, 0ⁿ1ⁿär CFL, eftersom vilken sträng som helst kan vara resultatet av pumpning på två ställen, en för 0 och en annan för 1. Låt oss bevisa, L₀₁₂= n ? 0 är inte kontextfri. Låt oss anta att L är kontextfri, sedan följer ovanstående givna regler genom Pumping Lemma. Låt nu x? L och |x| ? n. Så, genom att pumpa Lemma, finns det u, v, w, x, y så att (1) – (3) håller. Vi visar att u, v, w, x, y (1) – (3) inte håller. Om (1) och (2) håller är x = 0ⁿ1ⁿ2ⁿ= uvwxy med |vwx| ? n och |vx| ? 1. (1) säger oss att vwx inte innehåller både 0 och 2. Således har antingen vwx inga 0:or, eller så har vwx inga 2:or. Därför har vi två fall att överväga. Anta att vwx inte har några nollor. Med (2) innehåller vx en 1:a eller en 2:a. Uwy har alltså 'n' 0:or och uwy har antingen mindre än 'n' 1:or eller mindre än 'n' 2:or. Men (3) säger oss att uwy = uv⁰wx⁰y ? L. Så, uwy har lika många 0:or, 1:or och 2:or ger oss en motsägelse. Fallet där vwx inte har några 2:or är liknande och ger oss också en motsägelse. L är alltså inte kontextfri. Källa: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Introduktion till automatteori, språk och beräkningar.

Denna artikel har bidragit av Nirupam Singh .