Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky

Domáce Hardware Siete Programovanie Softvér Otázka Systémy

Ako sa dá použiť čerpacia lemma na preukázanie toho, že jazyk nie je kontext bez kontextu?

Čerpacia lemma pre jazyky bez kontextov (CFL) je výkonným nástrojom na preukázanie toho, že daný jazyk nie je * bez kontextu. Je to dôkaz techniky protirečenia. Tu je všeobecný proces a kľúčové nápady:

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 i

xy i

z* je tiež v L (čerpanie 'v' a 'y', ktorýkoľvek koľkokrát udržuje reťazec v jazyku)

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 i

xy i

z * nie je * v * l
*

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 xy i

z*nie je*v jazyku*l*. To znamená, že porušuje pravidlá, ktoré definujú reťazce patriace k jazyku.

* Ako ukázať * uv i

xy i

z * nie je v * l
*:Závisí to od konkrétneho jazyka. Budete musieť preukázať, že čerpaný reťazec porušuje definujúce vlastnosti *l *. Bežné stratégie zahŕňajú:

* 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 B

n C n | n ≥ 0}

Dokážme, že * l * ={a

n B

n C n | n ≥ 0} nie je bez kontextu pomocou čerpacej lemmy.

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 *p* . Je zrejmé, že*S*∈*L*a |*S*| =3*p*≥*p*.

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 j

a * y * =a k Pre niektorých*j*,*k*≥ 0 a*j + k*≥ 1. Ak prečerpáme (*i*=0), dostaneme reťazec a

*p-j-k* B

*p* C *p* . Od * j + k * ≥ 1 má tento reťazec menej ako * p * 'a, ale stále má * p *' b's a * p * 'c's. Preto nie je v *l *.

* Prípad 2:* vxy * pozostáva iba z 'b's. Potom * v * =b j

a * y * =b k Pre niektorých*j*,*k*≥ 0 a*j + k*≥ 1. Ak prečerpáme (*i*=0), dostaneme *p*
b *p-j-k* C *p* . Opäť platí, že počet 'B je menší ako *p *, zatiaľ čo čísla' A a 'C's zostávajú *p *, takže to nie je v *l *.

* Prípad 3:* vxy * pozostáva iba z 'c's. Potom * v * =c j

a * y * =c k Pre niektorých*j*,*k*≥ 0 a*j + k*≥ 1. Ak prečerpáme (*i*=0), dostaneme *p* B

*p* C *p-j-k* . Počet 'c je menší ako *p *, zatiaľ čo čísla' A a 'B zostávajú *p *, takže to nie je v *l *.

* 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 l B

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+k+m* C *p* . Ak * k + m * je nula (tak * v * a * y * obsahuje iba „A) počet„ A sa zvýši, ale počet “zostane rovnaký. Výsledkom je *p+j+l*

B

*p* C *p* ktorý už nie je v jazyku. Ak * J + L * je nula (So * V * a * y * obsahuje iba 'B), počet' B sa zvyšuje, ale počet 'A zostane rovnaký. Výsledkom je *p* b *p+k+m* C *p* ktorý už nie je v jazyku. Ak sú *k+m *a *j+l *väčšie ako nula, potom *uv 2

XY

2 Z* má viac 'A a' B ako 'c's, čo znamená, že to nemôže byť vo forme n B

n C n .

* 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 i

xy i

z*nie je v*l*. To je v rozpore s čerpacou lemmou.

6. Záver: Náš počiatočný predpoklad, že * l * je bez kontextu, musí byť nepravdivý. Tak, * l * ={a

n B

n C n | n ≥ 0} nie je bez kontextu.

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!

Najnovšie články

Copyright © počítačové znalosti Všetky práva vyhradené