Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Uveďte čerpaciu lemmu (opatrne!)
Predtým, ako začnete, je nevyhnutné porozumieť tomu, aby ste čerpalo Lemmu vyhlásenie *presne *. Tu je spoločná formulácia:
Pumpovanie Lemma pre CFL:
Ak L je jazyk bez kontextu, potom existuje celé číslo *p *(„dĺžka čerpania“) tak, že pre akýkoľvek reťazec *s *v l s dĺžkou väčšou alebo rovnajúcou sa *p *(| s | ≥ *p *), *s *sa dá rozdeliť do piatich podretier:*s =uvxyz *, spĺňanie nasledujúcich podmienok:
* | vxy | ≤ * p * (čerpaná stredná časť nie je príliš dlhá)
* | vy ≥ 1 (čerpaná sekcia nie je prázdna)
* Pre všetkých * i * ≥ 0, * uv
2. Predpokladajme, že jazyk * je * bez kontextu
Začnite tým, že sa predpokladá, že v záujme rozporu, že jazyk *L *Chcete dokázať, že je *nie *bez kontextu *je *v skutočnosti bez kontextu. Toto je počiatočný predpoklad, že nakoniec vyvrátite.
3. Nech * p * je dĺžka čerpania
Pretože ste predpokladali, že * L * je bez kontextu, musí sa použiť čerpacia lemma *. To znamená, že existuje čerpacia dĺžka * p * (ktorú nepoznáte presnú hodnotu). Je nevyhnutné pamätať na to, že protivník (kto vie, že jazyk nie je *bez kontextu a snaží sa vás oklamať) si môže vybrať *p *. Vaším cieľom je nájsť reťazec, ktorý * bez ohľadu na to, aká hodnota P * je vybraná, podmienky čerpacej lemmy vedú k rozporu.
4. Vyberte reťazec*s*∈*l*tak, aby |*s*| ≥ *p *
Toto je kritický krok. Musíte si starostlivo vybrať reťazec *S *, ktorý patrí do jazyka *L *a má dĺžku väčšiu alebo rovnú *p *. Výber * S * je rozhodujúci pre to, aby bol dôkaz fungoval. Zamyslite sa nad štruktúrou reťazcov vo vašom jazyku a o tom, ako môže čerpanie ovplyvniť túto štruktúru. Cieľom je vybrať reťazec, ktorého vlastnosti budú porušené, keď sa „v“ a „y“ čerpajú spôsobom diktovaným čerpacou lemmou. Táto voľba *často *zahŕňa nastavenie niektorých častí reťazca na základe hodnoty *p *.
*Premýšľajte o vlastnostiach, ktoré k nemu patria reťazce v jazyku. Potom vyberte reťazec takým spôsobom, že keď sa čerpá akákoľvek čiastková reťazca, porušuje sa aspoň jedno z obmedzení pre členstvo v jazyku.*
5. Zvážte všetky možné rozklady * s =uvxyz * uspokojujúce | vxy | ≤ * p * a | vy ≥ 1
Pumping Lemma uvádza, že*akýkoľvek*reťazec*s*s |*s*| ≥ * p * sa dá rozdeliť týmto spôsobom. Takže, váš protivník * si vyberie, ako je * s * rozdelený na * uvxyz * (podlieha obmedzeniam | vxy | ≤ * p * a | vy | ≥ 1). Zohľadníte však všetky možné takéto divízie. Musíte ukázať, že *bez ohľadu na to, ako *protivník vyberie *u *, *v *, *x *, *y *a *z *, môžete napumpovať reťazec, aby ste dostali rozpor.
Často to zahŕňa zváženie rôznych *prípadov *na základe toho, kde *v *a *y *by potenciálne mohlo spadnúť do reťazca *s *. V každom prípade budete analyzovať, čo sa stane, keď pumpujete *v *a *y *.
6. Ukážte, že pre niektorých *i *≥ 0, reťazec *uv
Toto je jadro rozporu. Pre každý prípad, ktorý sa uvažoval v kroku 5, musíte ukázať, že existujú nejaké *i *(zvyčajne *i *=0 alebo *i *=2, ale niekedy sú potrebné iné hodnoty), takže výsledný reťazec *uv
i
* Ako ukázať * uv
* ukazuje, že reťazec má teraz nerovnaké počty symbolov, ktoré boli predtým rovné. Napríklad, ak * L * vyžaduje rovnaký počet „A a“ B, ukážete, že čerpanie spôsobuje, že počet je nerovnaký.
* ukazuje, že poradie symbolov je teraz nesprávne. Napríklad, ak * L * vyžaduje, aby všetky „A boli pred všetky„ B, ukážete, že čerpanie môže dať „B“ pred „A“.
* ukazuje, že matematický vzťah medzi počtom už neplatí. Napríklad, ak * L * vyžaduje, aby počet 'A, aby bol dvojnásobkom počtu' B, ukážete, že čerpanie porušuje tento vzťah.
7. Záver, že * L * nie je * nie * bez kontextu
Pretože ste ukázali, že predpoklad, že * L * je bez kontextu, vedie k rozporu (čerpacia lemma musí držať, ale ukázali ste prípad, kde nie), môžete dospieť k záveru, že váš počiatočný predpoklad bol nepravdivý. Preto * L * nie je jazykom bez kontextu.
Príklad:Jazyk l ={a
n
n
Dokážme, že * l * ={a
n
n
C
1. Predpokladajme * l * je bez kontextu.
2. Nech * p * je dĺžka čerpania zaručené čerpacou lemmou.
3. Vyberte reťazec *S *: Nech*s*=a
*p* B
*p*
C
4. Zvážte všetky možné divízie * s =uvxyz * také, že | vxy | ≤ * p * a | vy ≥ 1: Musíme zvážiť, kde sa podrzy *v *a *y *môžu nachádzať v *s *. Kľúčovým obmedzením je, že vxy | ≤ *p *. To výrazne obmedzuje možnosti:
* Prípad 1:* vxy * pozostáva iba z 'a. Potom * v * =a
*p-j-k* B
*p*
C
* Prípad 2:* vxy * pozostáva iba z 'b's. Potom * v * =b
* Prípad 3:* vxy * pozostáva iba z 'c's. Potom * v * =c
*p*
C
* Prípad 4:* vxy * pozostáva z 'a a' b's. Pretože | vxy | ≤ *p *, nemôže obsahovať žiadne 'c, pretože všetky *p *' a a *p *'b's musia predchádzať akémukoľvek' c's. Pretože | vy ≥ 1, aspoň jeden z * v * alebo * y * musí obsahovať znak. Preto * v * =a
j
B
k
a * y * =a
m Pre niektorých *j *, *k *, *l *, *m *≥ 0 a *j + k + l + m *≥ 1, aspoň jedným z 'a' alebo 'b' v buď *v *alebo *y *.
Ak čerpíme (*i*=2), dostaneme reťazec *p+j+l*
b*p*
C
2
Z* má viac 'A a' B ako 'c's, čo znamená, že to nemôže byť vo forme
n
B n
C
* Prípad 5:* Vxy * sa skladá z 'B's a' C's. Toto je symetrické pre prípad 4. Opäť bude čerpanie vyústili do reťazca, ktorý nie je v jazyku.
5. protirečenie: V každom možnom prípade sme ukázali, že existuje *i *tak, že *uv
6. Záver: Náš počiatočný predpoklad, že * l * je bez kontextu, musí byť nepravdivý. Tak, * l * ={a
n
B n
C
Tipy na kľúč na použitie čerpacej lemmy:
* Pochopte lemmu presne: Poznať presné vyhlásenie a podmienky.
* Strategický výber reťazca: Výber * S * je rozhodujúci. Vyberte reťazec, ktorý zvýrazňuje vlastnosť, ktorú chcete prelomiť čerpaním. Nastavenie častí reťazca na základe * p * je často užitočné.
* starostlivá analýza prípadov: Zvážte všetky možné miesta pre *v *a *y *vo vnútri *s *, vzhľadom na obmedzenia | vxy | ≤ * p * a | vy ≥ 1.
* Vyberte správne * i *:Experiment s *i *=0, *i *=2 alebo inými hodnotami, aby ste našli ten, ktorý najjasnejšie demonštruje porušenie *l *. Niekedy * i * =0 spôsobí, že niečo zmizne a * i * =2 spôsobí niečo duplikované.
* Buďte jasní a prísne: Vysvetlite presne, prečo čerpaný reťazec už nie je v *L *. Pozrite si definujúce vlastnosti jazyka.
Čerpacia lemma môže byť zložitejšia na zvládnutie. Cvičte s rôznymi jazykmi, aby ste získali skúsenosti pri výbere vhodných reťazcov a riešení analýzy prípadov. Pamätajte, že cieľom je nájsť reťazec, kde * akákoľvek možná aplikácia čerpacej lemmy vedie k rozporu. Veľa šťastia!