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

Ako je možné preukázať, že jazyk nie je bez kontextu?

Existuje niekoľko spôsobov, ako preukázať, že jazyk nie je bez kontextu. Najbežnejšie metódy sa spoliehajú na preukázanie jazyka porušuje vlastnosti spojené s jazykmi bez kontextu (CFL):

1. Čerpanie lemmy pre jazyky bez kontextu: Toto je najčastejšie používaná technika. Pumping Lemma uvádza, že pre akýkoľvek cfl l existuje konštanta * p * (dĺžka čerpania) tak, že akýkoľvek reťazec * w * v l s dĺžkou | w | ≥ *p *je možné písať ako *uvxyz *, kde:

* | vxy | ≤ *p *

* | vy ≥ 1

* * uv i

xy i

z* ∈ L pre všetkých* i* ≥ 0

Na preukázanie jazyka nie je * nie * bez kontextu pomocou čerpacej lemmy:

1. Predpokladajme: Z dôvodu rozporu predpokladajte, že jazyk * l * je bez kontextu.

2. Vyberte reťazec: Vyberte reťazec *w *v *l *s dĺžkou aspoň dĺžkou čerpania *p *(často budete musieť strategicky zvoliť *w *).

3. Pumpujte reťazec: Pokúste sa rozložiť * w * do * uvxyz * uspokojiť podmienky Lemmy.

4. Nájdite rozpor: Ukáž to pre niektorých *i *, *uv i

xy i

z*nie je*v*l*. To je v rozpore s čerpacou lemmou, čo dokazuje, že pôvodný predpoklad (že * L * je bez kontextu) musí byť nepravdivý.

Príklad: Zoberme si jazyk l ={a

n B

n C n | n ≥ 0}. Pomocou čerpacej lemmy:

1. Predpokladajme: L je bez kontextu.

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

p C p (kde * p * je dĺžka čerpania).

3. Pumpujte reťazec: Bez ohľadu na to, ako sa rozkladáte *w *do *uvxyz *, čerpanie nevyhnutne poruší A

n B

n C n štruktúra. Napríklad, ak * vxy * obsahuje iba „A, čerpanie zvýši počet„ A's bez zvýšenia počtu „B a“ C. Podobné problémy sa vyskytujú, ak * vxy * obsahuje iba „B alebo“ alebo zmes, ktorá neudržiava rovnaký pomer.

4. protirečenie: Preto existuje *i *tak, že *uv i

xy i

z* ∉ l, v rozpore s čerpacou lemmou. L nie je kontext bez kontextu.

2. Vlastnosti uzavretia: Jazyky bez kontextu sú uzavreté pri určitých operáciách (Únia, zreťazenie, Kleene Star, križovatka s pravidelným jazykom). Ak dokážete ukázať, že jazyk nie je v rámci jednej z týchto operácií uzavretý, nemôže byť bez kontextu. Táto metóda sa menej často používa na priamy dôkaz ako čerpacia lemma, ale môže byť užitočná v kombinácii s inými technikami.

3. Ogden's Lemma: Toto je výkonnejšia verzia čerpacej lemmy, ktorá vám umožňuje zvoliť si značné pozície v rámci reťazca *w *. Je to užitočné pre jazyky, v ktorých je ťažké uplatniť jednoduchú čerpaciu lemmu.

4. Parikhova veta: Táto veta sa týka počtu výskytov každého symbolu v reťazci jazyka. Aj keď sa priamo nepoužíva na preukázanie jazyka * nie je bez kontextu, niekedy môže pomôcť ukázať, že štruktúra jazyka je nezlučiteľná s obmedzeniami uloženými CFL. Často sa používa v spojení s inými technikami.

Stručne povedané, čerpacia lemma je najbežnejšou a všeobecne efektívnejšou metódou na preukázanie jazyka nie je kontext bez kontextu. Výber metódy však závisí od štruktúry konkrétneho jazyka a od ľahkosti, s akou je možné použiť každú techniku. Ogden's Lemma v prípade potreby ponúka viac energie a vlastnosti uzavretia môžu poskytnúť doplnkové dôkazy.

Predchádzajúca strana: Čo je postup v kóde a ako používal programovacie jazyky?
Ďalšia strana: Aké sú príklady Turingovcov rozpoznateľných jazykov a ako sa líšia od iných typov jazykov?

Ako je možné preukázať, že jazyk nie je bez kontextu?

Odporúčané články

Najnovšie články

Počítač Programovacie jazyky