Ako môžete pomocou čerpacej lemmy dokázať, že jazyk nie je pravidelný?

Čerpacia lemma pre bežné jazyky je výkonným nástrojom na preukázanie toho, že jazyk nie je * pravidelný. Funguje to v rozpore:predpokladáte, že jazyk * je * pravidelný a potom ukážete, že tento predpoklad vedie k rozporu samotnej lemmy. Takto to funguje:

1. Vyhlásenie o čerpacej lemme:

Pumping Lemma uvádza, že pre akýkoľvek pravidelný jazyk L existuje čerpacia dĺžka p tak, že akýkoľvek reťazec w v l s dĺžkou | w | ≥ P možno rozdeliť na tri podrestvá, w =xyz, splnenie nasledujúcich podmienok:

* | XY | ≤ p: Dĺžka zreťazenia x a y je menšia alebo rovná p.

* | y |> 0: Podrestčka y nie je prázdna.

* Pre všetky i ≥ 0, xy

i

z ∈ L: Čerpanie y nula alebo viackrát (vrátane jeho úplného odstránenia, keď i =0) vedie k reťazcu, ktorý je stále v jazyku L.

2. Dôkazná stratégia:

Aby ste dokázali, že jazyk L nie je pravidelné používať čerpaciu lemmu, postupujte podľa týchto krokov:

* Predpokladajme, že l je pravidelné: Začnite tým, že za protirečenie predpokladáte, že L je pravidelný jazyk.

* Vyberte čerpaciu dĺžku p: Čerpacia lemma zaručuje existenciu čerpacej dĺžky p; Nemusíte nájsť svoju skutočnú hodnotu, iba ju označujte ako „p“.

* Vyberte reťazec w ∈ L tak, aby | w | ≥ p: Opatrne vyberte reťazec w z jazyka L, ktorého dĺžka je aspoň s. Výber W je rozhodujúci; Musí vám umožniť v ďalšom kroku vytvoriť rozpor. To často zahŕňa reťazce so špecifickou štruktúrou súvisiacou s definíciou jazyka.

* ukazuje, že žiadny rozklad w =xyz spĺňa podmienky čerpacieho lemmy: Toto je srdce dôkazu. Pre * akýkoľvek * možný rozklad w do XYZ uspokojujúce | xy | ≤ p a | y |> 0, musíte ukázať, že existujú niektoré I ≥ 0 tak, že xy

i

Z ∉ L. To znamená, že čerpanie Y porušuje definíciu jazyka L. Často to demonštrujete tým, že ukážete, že čerpanie y bude buď:

* Predstavujte nerovnováhu: Zmeňte počet výskytov niektorých symbolov a porušuje obmedzenie počítania v L.

* Vytvorte neplatnú štruktúru: Rozložte vzor alebo štruktúru požadovanú v definícii L.

* Predstavte neplatný podrestík: Vytvorte oddiel, ktorý nepatrí do jazyka.

* dospieť k záveru, že L nie je pravidelný: Pretože ste ukázali, že pre zvolený reťazec w nemôže existovať žiadny taký rozklad, je to v rozpore s čerpacou lemmou. Počiatočný predpoklad, že L je pravidelný, musí byť nepravdivý a L nie je pravidelný.

Príklad:Proving {a n B

n | n ≥ 0} nie je pravidelné:

Nech l ={a n B

n | n ≥ 0}.

1. Predpokladajme, že l je pravidelný.

2. Vyberte p: Nech P je dĺžka čerpania.

3. Vyberte w: Nech w =a

p B

p . Je zrejmé, že w ∈ L a | W | ≥ s.

4. Neukazuje žiadny rozklad nespĺňa podmienky: Zvážme akýkoľvek rozklad w =xyz taký, že | xy | ≤ p a | y |> 0. Pretože | xy | ≤ p, y musí pozostávať iba * z A (pretože y je podrestčka z prvých znakov P). Y =a

k Pre niektorých k> 0. Teraz pump y nula časy:xy

0

z =a p-k B

p . Tento reťazec nie je v L, pretože počet A a B je iný. To je v rozpore s čerpacou lemmou.

5. záver: Keďže sme dosiahli rozpor, náš predpoklad, že L je pravidelný, musí byť nepravdivý. Preto l ={a n B

n | n ≥ 0} nie je pravidelný jazyk.

Kľúčom je starostlivo zvoliť reťazec `W` a šikovne analyzovať všetky možné rozklady` xyz`, aby ste ukázali, že čerpanie `y` vždy vedie k reťazcu mimo jazyka. Čím zložitejší jazyk, tým zložitejší výber `W` a analýza sa stane.

• Predchádzajúca strana: Ako môžete definovať a manipulovať s reťazcovými skalarmi v programovacích jazykoch? 
• Ďalšia strana: Aké sú bežné aplikácie operátora modulu v programovacích jazykoch?