* počítačové znalosti >> Programovanie >> Počítač Programovacie jazyky >> .

Ako sa dá použiť čerpacia lemma na preukázanie toho, že nasledujúce jazyky nie sú kontextové?

Čerpacia lemma pre jazyky bez kontextu je výkonným nástrojom, ktorý dokáže, že jazyk nie je * bez kontextu. Funguje to v rozpore:predpokladáme, že jazyk * je bez kontextu bez kontextu a potom ukážeme, že tento predpoklad vedie k rozporu. Tu je návod, ako sa to uplatňuje, spolu s príkladmi:

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

z* je v L.

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 B

n C n | n ≥ 0}

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 p *, kde *p *je dĺžka čerpania. | W | ≥ *p *.

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 i

xy i

z* je v l₁ pre všetkých* i* ≥ 0.

5. Záver: Preto L₁ nie je bez kontextu.

2. L₂ ={a n B

m C n+m | n, m ≥ 0}

1. Predpokladajme, že l₂ je bez kontextu.

2. Vyberte reťazec w: Nech *w =a

p B

p C 2p *.

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 B

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.

Predchádzajúca strana: Ako je možné dokázať, že jazyk je rozhodujúci?
Ďalšia strana: Ako môžem zlepšiť svoje zručnosti v oblasti spracovania prirodzeného jazyka prostredníctvom tréningu GPT-4?

Ako sa dá použiť čerpacia lemma na preukázanie toho, že nasledujúce jazyky nie sú kontextové?

Odporúčané články

Najnovšie články

Počítač Programovacie jazyky