Ir divas sūknēšanas lemmas, kas ir definētas 1. parastajām valodām un 2. kontekstam — brīvajām valodām. Lemmas sagatavošana parastajām valodām Jebkurai regulārai valodai L eksistē vesels skaitlis n, tā ka visiem x ? L ar |x| ? n, pastāv u, v, w ? ?^*, lai x = uvw, un (1) |uv| ? n (2) |v| ? 1 (3) visiem i ? 0: uvⁱw ? L Vienkārši izsakoties, tas nozīmē, ka, ja virkne v tiek “iesūknēta”, t.i., ja v tiek ievietots jebkādu skaitu reižu, iegūtā virkne joprojām paliek L. Sūknēšanas lemma tiek izmantota kā valodas neregularitātes pierādījums. Tādējādi, ja valoda ir regulāra, tā vienmēr apmierina pumpēšanas lemmu. Ja eksistē vismaz viena virkne, kas izgatavota no sūknēšanas, kas nav L, tad L noteikti nav regulāra. Pretējs tam ne vienmēr var būt taisnība. Tas ir, ja Pumping Lemma ir spēkā, tas nenozīmē, ka valoda ir regulāra.

Piemēram, pierādīsim L₀₁= n? 0 ir neregulārs. Pieņemsim, ka L ir regulārs, tad, sūknējot Lemmu, tiek ievēroti iepriekš minētie noteikumi. Tagad ļaujiet x? L un |x| ? n. Tātad, sūknējot Lemmu, pastāv u, v, w tā, ka (1) – (3) ir spēkā. Parādām, ka uz visiem u, v, w, (1) – (3) neatbilst. Ja (1) un (2) ir spēkā, tad x = 0ⁿ1ⁿ= uvw ar |uv| ? n un |v| ? 1. Tātad u = 0^a, v = 0^b, w = 0^c1ⁿkur: a + b? n, b? 1, c ? 0, a + b + c = n Bet, tad (3) neizdodas, ja i = 0 uv⁰w = uw = 0^a0^c1ⁿ= 0^{a + c}1ⁿ? L, jo a + c ? n.

Lemmas izsūknēšana bezkontekstu valodām (CFL) Pumping Lemma for CFL nosaka, ka jebkurai konteksta brīvai valodai L ir iespējams atrast divas apakšvirknes, kuras var “iesūknēt” neierobežotu skaitu reižu un joprojām ir vienā valodā. Jebkurai valodai L mēs sadalām tās virknes piecās daļās un sūknējam otro un ceturto apakšvirkni. Sūknēšana Lemma arī šeit tiek izmantota kā rīks, lai pierādītu, ka valoda nav CFL. Jo, ja kāda virkne neatbilst tās nosacījumiem, tad valoda nav CFL. Tādējādi, ja L ir CFL, pastāv vesels skaitlis n, tā ka visiem x ? L ar |x| ? n, pastāv u, v, w, x, y? ?^*, lai x = uvwxy un (1) |vwx| ? n (2) |vx| ? 1 (3) visiem i ? 0: uvⁱwxⁱun ? l

Iepriekš minētajam piemēram, 0ⁿ1ⁿir CFL, jo jebkura virkne var būt rezultāts sūknēšanai divās vietās, viena ir 0 un otra 1. Pierādīsim, L₀₁₂= n? 0 nav bez konteksta. Pieņemsim, ka L ir bez konteksta, tad, sūknējot Lemmu, tiek ievēroti iepriekš minētie noteikumi. Tagad ļaujiet x? L un |x| ? n. Tātad, sūknējot Lemmu, pastāv u, v, w, x, y, kas atbilst (1) – (3). Mēs parādām, ka visiem u, v, w, x, y (1) – (3) nav spēkā. Ja (1) un (2) ir spēkā, tad x = 0ⁿ1ⁿ2ⁿ= uvwxy ar |vwx| ? n un |vx| ? 1. (1) norāda, ka vwx nesatur gan 0, gan 2. Tādējādi vai nu vwx nav 0, vai vwx nav 2. Tādējādi mums ir jāapsver divi gadījumi. Pieņemsim, ka vwx nav 0. Ar (2) vx satur 1 vai 2. Tādējādi uwy ir 'n' 0 un uwy vai nu ir mazāks par 'n' 1, vai ir mazāks par 'n' 2'. Bet (3) norāda, ka uwy = uv⁰wx⁰y ? L. Tātad, uwy ir vienāds skaits 0, 1 un 2, rada mums pretrunu. Gadījums, kad vwx nav 2, ir līdzīgs un arī rada mums pretrunu. Tādējādi L nav bez konteksta. Avots: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Ievads automātu teorijā, valodās un aprēķinos.

Šo rakstu ir sagatavojis Nirupams Sings .