Chomského hierarchia jazykov

Vysvetlíme si rôzne typy gramatík a pravidiel zápisu, Chomského hierarchiu a predstavíme si zložitejšie úlohy pre tvorbu gramatík a jazykov.

Chomského hierarchia gramatík

Gramatiky, ktoré sme si predstavili v predošlej téme mali zmiešané typy. Gramatiky ale môžeme rozlíšiť podľa ich spôsobu zápisu pravidiel do rôznych kategórií.{{#display_diagram:Drawio:Chomského hierarchia gramatík}}V roku 1956 Noam Chomsky položil základy pre túto hierarchiu vo svojej práci ("Three models for the description of language"). Cieľom práce bolo skúmať spôsoby, akým by bolo možné vytvoriť formálnu gramatiku ktorá generuje všetky platné lingvistické konštrukcie v anglickom jazyku.

Neskôr sa dospelo k záveru, že jazyky majú vo všeobecnosti nasledovnú hierarchiu:

0. typ: 🔃 rekurzívne enumerovateľné gramatiky - bez reštrikcií pre tvorbu pravidiel, pravá strana pravidla môže byť kratšia ako ľavá (symboly môžme mazať. Sú to najvoľnejšie typy gramatík, chápe im iba Turingov stroj (ale typy automatov si vysvetlíme až neskôr).
   Napr.: $aabbaa\to a{S}_{0}a{S}_{0}df$ alebo $S_{0}livka\to a{S}_{0}d{S}_{0}fdaf$.
1. typ: 🧠 kontextové gramatiky - ľavá strana pravidla musí obsahovať aspoň jeden neterminálny symbol a pravá strana musí obsahovať aspoň jeden neprázdny terminálny alebo neterminálny symbol. Pravá strana pravidla musí byť dlhšia ako ľavá (symboly nemôžme mazať, teda tieto dve pravidlá sem nepatria: $abba\to b$, $abba\to ϵ$). Tieto typy gramatík sa používajú najčastejšie pre popis syntaxe programovacích jazykov.
   Napr.: $a{S}_{0}b\to aab$ alebo $a{S}_{0}b\to b{S}_{0}a$.
2. typ: 🔀 bezkontextové gramatiky - ľavá strana pravidla musí obsahovať práve jeden neterminálny symbol a pravá strana pravidla musí obsahovať aspoň jeden terminálny alebo neterminálny symbol.
   Napr.: $S_0\to a{S}_{0}bc{S}_{0}a$.
3. typ: ➡️ regulárne gramatiky - najviac reštriktívne gramatiky. Ľavá strana pravidla musí obsahovať práve jeden neterminálny symbol a pravá strana pravidla musí obsahovať maximálne jeden neterminálny symbol za ktorým nasleduje ihneď práve jeden terminálny symbol.
   Napr.: $S_0\to a{S}_0$ alebo $S_0\to a$.

ℹ️

Možno si si všimol, že neterminálny symbol je zapísaný ako $S_0$ namiesto iba $S$. Je to z toho dôvodu, aby sme jednoznačne vedeli odlíšiť tento neterminálny symbol od klasického písmena "S" ktoré nájdeme v abecede. Odteraz budeme vždy používať jednoznačné označenie pre neterminály (teda budeme používať indexy).

Platí, že jednotlivé typy gramatík sú hierarchiou podmnožín. Napríklad, 🧠 kontextové gramatiky a 🔀 bezkontextové gramatiky spĺňajú kritériá pravidiel pre ➡️ regulárne gramatiky (ale nie naopak). Ak sa pozrieš na spôsoby zápisu pravidiel zdola hore, budeš vidieť ako sa postupne stávajú voľnejšími a pravidlá tým pádom môžu byť zložitejšie (viac rekurzie, a podobne).

Referencie

« Gramatika vo formálnych jazykoch

Pokročilé úlohy pre tvorbu gramatík »