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.

Dospelo sa k záveru, že jazyky majú vo všeobecnosti nasledovnú hierarchiu:

0. typ: 🔃 rekurzívne enumerovateľné gramatiky - bez reštrikcií pre tvorbu pravidiel (s výnimkou, že ľavá strana / pred šípkou musí mať minimálne jeden terminálny alebo neterminálny symbol, inak by pravidlo nedávalo zmysel pretože by sme nevedeli čo sa má vôbec prepísať).
1. Napr.: $aabbaa\to a{S}_{0}a{S}_{0}df$ alebo $S_{0}livka\to a{S}_{0}d{S}_{0}fdaf$
2. 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.
3. Používajú sa najčastejšie pre popis syntaxe programovacích jazykov.
4. Napr.: $a{S}_{0}b\to aab$
5. 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.
6. Napr.: $S_0\to a{S}_{0}bc{S}_{0}a$
7. 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 ihneď nasleduje práve jeden terminálny symbol.
8. 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.

Referencie

« Úvod do formálnych jazykov

Chomského hierarchia jazykov »