Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Čerpacia lemma (pre CFL):
Ak L je jazyk bez kontextu, existuje konštanta * p * (dĺžka čerpania) tak, že akýkoľvek reťazec * w * v l s | w | ≥ *p *je možné písať ako *w =uvxyz *, kde:
1. | Vxy | ≤ *p *
2. | Vy ≥ 1
3. Pre všetkých *i *≥ 0, *uv
xy
Dôkaznou stratégiou je nájsť reťazec *W *v jazyku tak, že bez ohľadu na to, ako ho rozkladáme do *uvxyz *uspokojí podmienky Lemmy, a čerpanie (zvýšenie *i *) vytvorí reťazec, ktorý nie je *v jazyku. To je v rozpore s lemmou, čo dokazuje, že jazyk nie je kontext bez kontextu.
Príklady:
Uvádzajme s niekoľkými príkladmi jazykov a ako dokázať, že nie sú kontext bez kontextu pomocou čerpacej lemmy:
1. L₁ ={a
n
C
1. Predpokladajme, že l₁ je bez kontextu. To znamená, že sa uplatňuje čerpacia lemma.
2. Vyberte reťazec w: Vyberme si *w =a
p B
p
C
3. Pumpovanie: Pretože | vxy | ≤ *p *, *vxy *môže preklenúť najviac dve časti (aaa ... bbb ... ccc ...). Existujú tri možnosti:
* vxy obsahuje iba A a B: Čerpanie zmení počet A a/alebo B bez zmeny počtu C, čo bude mať za následok reťazec, ktorý nie je v L₁.
* vxy obsahuje iba B a C: Podobne ako vyššie, počet B a/alebo C sa zmení neprimerane.
* vxy obsahuje iba A: Čerpanie ovplyvní iba počet A.
4. protirečenie: Vo všetkých prípadoch čerpanie vytvára reťazec, ktorý nie je v L₁. To je v rozpore s čerpacím tvrdením Lemmy, že *uv
5. Záver: Preto L₁ nie je bez kontextu.
2. L₂ ={a
m
1. Predpokladajme, že l₂ je bez kontextu.
2. Vyberte reťazec w: Nech *w =a
p B
p
C
3. Pumpovanie: Opäť, | vxy | ≤ *p *. Možnosti sú podobné ako L₁:Ak * vxy * obsahuje iba A a B, čerpanie zmení počet A a B bez úmernej zmeny počtu C.
4. protirečenie: Čerpanie povedie k reťazcom, ktoré nie sú v L₂.
5. Záver: L₂ nie je kontext.
3. L₃ ={ww | w ∈ {a, b}*} (Jazyk reťazcov, ktoré sú zreťazením reťazca so sebou)
1. Predpokladajme, že l₃ je bez kontextu.
2. Vyberte reťazec w: Nech *w =a
p B
p
A
p *.
3. Pumpovanie: Pretože | vxy | ≤ *p *, *vxy *nemôže prekročiť stred reťazca (nemôže preklenúť obe polovice `ww`). Ak je * vxy * úplne v prvej polovici, čerpanie vyváži tieto dve polovice.
4. protirečenie: Čerpaný reťazec nebude v L₃.
5. Záver: L₃ nie je kontext.
Dôležité úvahy:
* Výber správneho reťazca *w *: To je rozhodujúce. Reťazec sa musí starostlivo zvoliť, aby využil obmedzenia uložené | vxy | ≤ *p *. Často sú užitočné reťazce s opakovanými vzormi.
* Manipulácia s všetkými prípadmi: Musíte zvážiť všetky možné spôsoby rozloženia * w * do * uvxyz * uspokojiť podmienky Lemmy a ukázať, že čerpanie vedie k rozporu v každom prípade.
* Dĺžka čerpania * p * je svojvoľná: Nepotrebujete poznať hodnotu *p *; Dôkaz funguje pre akýkoľvek *p *.
Starostlivým použitím týchto krokov môžete pomocou čerpacej lemmy ukázať, že mnoho jazykov nie je bez kontextu. Pamätajte, že čerpacia lemma poskytuje iba metódu na preukázanie jazykov * nie * bez kontextu; Nedá sa použiť na preukázanie toho, že jazyk * je * bez kontextu.