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 je možné preukázať, že jazyk neobsahuje kontext?

Existuje niekoľko spôsobov, ako preukázať, že jazyk je bez kontextu. Tu je rozpis spoločných techník a úvah:

1. Poskytnite gramatiku bez kontextu (CFG):

* Najpriamejšia a najpoužívanejšia metóda. Ak dokážete navrhnúť CFG, ktorý generuje * presne * reťazce v jazyku, dokázali ste, že je bez kontextu.

* CFG Definícia: CFG pozostáva z:

* * Non-terminály (premenné):* Zastúpené veľkými písmenami (napr. `S`,` a`, `b`).

* * Terminály:* Symboly abecedy jazyka (napr. `A`,` B`, `0", `1").

* * Symbol spustenia:* Rozlišovaný nekonečný (zvyčajne `S`).

* * Pravidlá výroby:* Pravidlá formulára `nekonemenálne -> reťazec terminálov a/alebo nekonementných“ (napr. `S -> ASB | ε`).

* Ako používať: Ukážte, že každý reťazec v jazyku je možné odvodiť od začiatočného symbolu pomocou výrobných pravidiel. Ukážte tiež, že gramatika * nevytvára žiadne reťazce, ktoré nie sú * v jazyku.

* Príklad:

* Jazyk:L ={a n B

n | n ≥ 0} (reťazce s rovnakým počtom „A's a 'B's, v tomto poradí)

* CFG:

* `S -> ASB | ε` (kde ε predstavuje prázdny reťazec)

* Vysvetlenie:

* `S` generuje základný vzor` asb`.

* Rekurzívnym uplatňovaním pravidla `S -> ASB` môžete vytvoriť ľubovoľný počet` a 'a `b', zabezpečením vyváženia.

* Pravidlo `s -> ε` vám umožňuje ukončiť rekurziu a vytvoriť prázdny reťazec (ktorý je tiež v jazyku, keď n =0).

2. Poskytnite automatický automat (PDA):

* ekvivalent s CFGS: Každý jazyk prijatý PDA je bez kontextu a naopak. Táto rovnocennosť je zásadným výsledkom teórie automatov.

* PDA Definícia: PDA je konečný automat so stohom. Dokáže čítať vstupné symboly, meniť jeho stav a vytlačiť symboly alebo popové symboly zo zásobníka.

* Ako používať: Navrhnite PDA, ktorý presne prijíma reťazce v jazyku. Stack sa často používa na sledovanie symbolov „neprekonaných“.

* Príklad (pre rovnaký jazyk l ={a

n B

n | n ≥ 0}):

* PDA znie 'A a tlačí ich do zásobníka.

* Keď sa stretne s „b“, objaví sa „A“ zo zásobníka.

* PDA akceptuje, či si prečítal všetky vstupy a zásobník je prázdny.

* Dôležité: Zadajte, ako prechádza PDA medzi stavmi na základe vstupných symbolov a obsahu zásobníka.

3. Používajte vlastnosti uzávierky:

* Jazyky bez kontextu sú uzavreté pri určitých operáciách. To znamená, že ak viete, že niektoré jazyky neobsahujú kontext, môžete ich kombinovať pomocou týchto operácií na vytvorenie nových jazykov bez kontextu.

* Vlastnosti uzavretia:

* únia: Ak sú L1 a L2 bez kontextu, L1 ∪ L2 je bez kontextu.

* zreťazenie: Ak sú L1 a L2 bez kontextu, L1L2 je bez kontextu.

* kleene hviezda ( *): Ak L je bez kontextu, potom L* je bez kontextu.

* homomorfizmus: Ak L je bez kontextu a `H` je homomorfizmus (funkcia, ktorá mapuje symboly na reťazce), potom` h (l) `je bez kontextu.

* inverzný homomorfizmus: Ak L je bez kontextu a `H` je homomorfizmus, potom` h -1

L) „je bez kontextu. (Inverzný homomorfizmus berie reťazec ako vstup a vracia sadu reťazcov, ktoré, keď sa aplikuje homomorfizmus, vám poskytne vstupný reťazec).

* Ako používať: Rozložte cieľový jazyk do jednoduchších jazykov, ktoré už viete *, sú bez kontextu, a potom ich skombinujte pomocou vlastností uzávierky.

* Príklad:

* Ukáž, že l ={a

n B

n C m D

m | N, M ≥ 0} je bez kontextu.

* L1 ={a n B

n | n ≥ 0} je bez kontextu (už to vieme).

* L2 ={c m D

m | M ≥ 0} je bez kontextu (podobne ako L1).

* L =L1L2 (zreťazenie L1 a L2).

* Pretože L1 a L2 sú bez kontextu a jazyky bez kontextu sú uzavreté v zreťazení, L je bez kontextu.

4. Čerpanie lemmy pre jazyky bez kontextu (na preukázanie jazyka je * nie * bez kontextu):

* Dôležité: Čerpacia lemma sa používa na * vyvrátenie *, že jazyk je bez kontextu. Nedá sa použiť na preukázanie toho, že jazyk * je * bez kontextu.

* Ako to funguje: Pumping Lemma uvádza, že pre akýkoľvek jazyk bez kontextu L existuje čerpacia dĺžka „p“, takže akýkoľvek reťazec 'v l s dĺžkou najmenej „p“ možno rozdeliť na päť častí, s =uvxyz, kde:

1. | Vxy | ≤ P (stredná časť nie je príliš dlhá)

2. | Vy ≥ 1 (časť, ktorá sa má opakovať, nie je prázdna)

3. Pre všetky I ≥ 0, UV xy i

Z je v L (môžete opakovať „v“ a „y“ ľubovoľný počet a výsledný reťazec je stále v jazyku).

* Protia protirečenie:

1. Predpokladajme, že jazyk je bez kontextu.

2. Predpokladajme, že existuje čerpacia dĺžka „p“, ako je opísané v lemme.

3. Vyberte reťazec v jazyku, ktorý je dlhší ako „p“. Výber „S“ je rozhodujúci. Mali by mať vlastnosti, vďaka ktorým je čerpanie problematické.

4. Zvážte * všetky možné * spôsoby, ako rozdeliť 's' na 'Uvxyz, ktoré spĺňajú podmienky 1 a 2 čerpacej lemmy.

5. Pre * každé * možné rozdelenie ukážte, že existuje 'i' (zvyčajne i =0 alebo i =2), takže UV i xy i

z nie je * v jazyku.

6. To je v rozpore s čerpacou lemmou, takže počiatočný predpoklad, že jazyk je bez kontextu, musí byť nepravdivý.

Ktorú metódu použiť:

* Grammar/PDA Construction: Najbežnejším a často najjednoduchším spôsobom, ako ukázať jazyk * je * bez kontextu. Vyberte si, čo (CFG alebo PDA) je ľahšie skonštruovať pre konkrétny jazyk. Ak sa zdá, že jazyk zahŕňa vnorené alebo rekurzívne štruktúry, gramatika je často dobrým východiskovým bodom. Ak sa jazyk dáva k správaniu podobným zásobníkov, zvážte použitie PDA.

* Vlastnosti uzavretia: Užitočné, keď je možné jazyk vyjadriť ako kombináciu jednoduchších, už známych jazykov bez kontextu.

* Pumpovanie Lemma: Výlučne na zobrazenie jazyka nie je * bez kontextu.

Dôležité úvahy:

* Pravidelné jazyky sú bez kontextu: Každý pravidelný jazyk je tiež bez kontextu. Ak dokážete ukázať, že jazyk je pravidelný (poskytnutím DFA, NFA alebo regulárneho výrazu), ukázali ste tiež, že je bez kontextu. CFG alebo PDA však často bude priamejším prístupom, ak je jazyk * očividne * bez kontextu.

* neterministické PDA: Všeobecne platí, že PDA sú nedeterministické. Deterministické PDA (DPDA) sú menej silné; Prijímajú správnu podmnožinu jazykov bez kontextu (nazývaných deterministické jazyky bez kontextu). Pokiaľ to nie je výslovne uvedené, môžete predpokladať, že máte čo do činenia so všeobecnými (nedeterministickými) kontextovými jazykmi.

* Dôkladná definícia: Či už navrhujete gramatiku alebo PDA, buďte veľmi presní vo svojich definíciách. Vyhnite sa nejednoznačnosti a jasne vysvetlite, ako vaša konštrukcia funguje.

* Príklady: Pracujte prostredníctvom mnohých príkladov, aby ste dosiahli dobré pochopenie týchto techník. Cvičenie je kľúčové!

Stručne povedané, * preukázať * jazyk je bez kontextu, zostavte preň CFG alebo PDA alebo demonštrujte jeho kontextovú voľnosť prostredníctvom vlastností uzavretia. Použite čerpaciu lemmu pre jazyky bez kontextu, aby ste ukázali, že jazyk nie je * bez kontextu. Veľa šťastia!

Najnovšie články

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