Taybetmendiya pompkirinê, ku wekî lemmaya pompkirinê jî tê zanîn, têgehek bingehîn e di warê teoriya tevliheviya hesabkirinê de, nemaze di lêkolîna zimanên hesas ên kontekstê de (CSL). Taybetmendiya pompkirinê şertek pêdivî peyda dike ku zimanek hestiyar be, û ew ji bo îsbatkirina hin zimanan ne hestiyar in arîkar dike.
Ji bo têgihîştina şert û mercên ku hewce ne ku ji bo xwedan milkê pompkirinê werin bicîh kirin, em pêşî pênase bikin ka zimanek hestiyar-aheng çi ye. Zimanek hestiyar-conteks zimanek fermî ye ku dikare ji hêla rêzimanek hestiyar-kontekst ve were çêkirin, ku celebek rêzimanê fermî ye ku rêgezên hilberînê destûr didin ku çarçoweya rêzika ku tê çêkirin biguhezînin. Bi gotineke din, rêziman dikare zimanên ku ji bo naskirina wan hin şêwazên konteksê hewce dikin nas bike û biafirîne.
Taybetmendiya pompkirinê ya ji bo zimanên hestiyar-kontekst, ku wekî lemma pompkirinê jî ji bo CSL-yan tê zanîn, diyar dike ku heke zimanek L-yê hestiyar-tewre be, wê hingê p domdar (dirêjahiya pompkirinê) heye ku her rêzek têra xwe dirêj w di L de dikare li pênc beşan bêne dabeş kirin: uvxyz, ku şertên jêrîn têr dike:
1. Dirêjahiya v û y ya hevgirtî ji sifirê mezintir e, ango, |vxy| > 0.
2. Dirêjahiya uvxy herî zêde p e, ango, |uvxy| ≤ p.
3. Ji bo her hejmara k ne-neyînî, rêzika uv^kxy^kz jî bi L ye.
Ji bo zelalkirina van şert û mercan, em mînakekê bidin ber çavan. Bifikirin ku me zimanek L = {a^nb^nc^n | n ≥ 0}, ku komek rêzikên ku ji jimarek wekhev a 'a', 'b' û 'c'ya bi wê rêzê pêk tê nîşan dide. Em dixwazin diyar bikin ka ev ziman taybetmendiya pompkirinê têr dike yan na.
Di vê rewşê de, dirêjahiya pompkirinê p dê bibe hejmara 'a', 'b' an 'c'yên ku dikarin werin pomp kirin. Ji bo sadebûnê em bêjin p = 2. Naha, rêzika w = a^2 b^2 c^2 bifikirin. Em dikarin vê rêzê wiha bikin pênc beş: u = a^2, v = b^2, x = ε (xêza vala), y = ε, û z = c^2.
Di vê rewşê de şertên taybetmendiya pompkirinê têne bicîh kirin:
1. Dirêjahiya v û y ya hevgirtî ji sifirê mezintir e, ji ber ku |vxy| = |b^2| > 0.
2. Dirêjahiya uvxyê herî zêde p e, ji ber ku |uvxy| = |a^2 b^2| ≤ 2.
3. Ji bo her jimareke ne-neyînî k, rêzika uv^kxy^kz jî di L de ye. Bo nimûne, heke em k = 0 hilbijêrin, hingê uv^0xy^0z = a^2 c^2, ku hîn jî di nav de ye. L.
Ji ber vê yekê em dikarin vê encamê bidin ku zimanê L = {a^nb^nc^n | n ≥ 0} taybetmendiya pompkirinê têr dike û hestiyar li ser kontekstê ye.
Bi gelemperî, şert û mercên ku milkê pompkirinê di çarçoweya CSL-yan de were girtin wiha ne:
1. Dirêjahiya v û y bi hev re divê ji sifirê mezintir be.
2. Dirêjahiya uvxy divê herî zêde dirêjahiya pompkirinê p be.
3. Ji bo her hejmara k ne-neyînî divê rêza uv^kxy^kz jî di zimanê L de be.
Van şertan destnîşan dikin ku heke zimanek li ser kontekstê hesas be, bi dûbarekirina beşek ji rêzê di heman demê de ku avahiya ziman diparêze dikare were "pomp kirin".
Pirs û bersivên din ên vê dawiyê di derbarê Zimanên Hêstiyar ên Naverok:
- Wateya wê çi ye ku zimanek ji yê din bi hêztir e?
- Rêzimana Chomsky ya normal her gav biryardar e?
- Ji bo naskirina Type-0 rêbazên heyî hene? Ma em li bendê ne ku komputerên quantum wê pêkan bikin?
- Di mînaka zimanê D de, çima taybetiya pompkirinê ji bo rêza S = 0^P 1^P 0^P 1^P nagire?
- Dema ku rêzek ji bo sepandina lemma pompkirinê tê dabeş kirin du doz çi ne?
- Di mînaka zimanê B de, çima taybetmendiya pompkirinê ji bo rêzika a^Pb^Pc^P nagire?
- Çawa dikare Lemma Pumping ji bo CFL-an were bikar anîn da ku îspat bike ku zimanek ne bê kontekst e?
- Ji bo ku zimanek li gorî lemmaya pompeyî ya ji bo zimanên bê-kontekst bêtevger were hesibandin şert û mercên ku divê werin bicîh kirin çi ne?
- Di çarçoweya rêzimanên bê kontekst de têgeha vegerandinê rave bike û ka ew çawa rê dide çêkirina rêzikên dirêj.
- Dara parse çi ye, û ew çawa tê bikar anîn da ku strukturek rêzek ku ji hêla rêzimanek bê kontekst ve hatî çêkirin temsîl bike?
Pirs û bersivan zêdetir di Zimanên Hessas Context de bibînin