Chomského hierarchia jazykov: Rozdiel medzi revíziami

Verzia z 14:38, 1. november 2024

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:

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.: $a a b b a a \to a S_{0} a S_{0} d f$ alebo $S_{0} l i v k a \to a S_{0} d S_{0} f d a f$ .
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: $a b b a \to b$ , $a b b a \to ϵ$ ). Tieto typy gramatík sa používajú najčastejšie pre popis syntaxe programovacích jazykov.
Napr.: $a S_{0} b \to a a b$ alebo $a S_{0} b \to b S_{0} a$ .
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} b c S_{0} a$ .
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

« Úvod do formálnych jazykov

Chomského hierarchia jazykov »

@@ Riadok 16: / Riadok 16: @@
 <li>typ: {{Štítok|emoji=🔀|text=bezkontextové gramatiky|farba=mediumpurple|farba_textu=black}} - ľ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.<br/>Napr.: <math>S_0 \rightarrow aS_0bcS_0a</math>.
-<li>typ: {{Štítok|emoji=➡️|text=regulárne gramatiky|farba=mediumseagreen|farba_textu=black}} - 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.<br/>Napr.: <math>S_0 \rightarrow aS_0</math> alebo <math>S_0 \rightarrow a</math>.
+<li>typ: {{Štítok|emoji=➡️|text=regulárne gramatiky|farba=mediumseagreen|farba_textu=black}} - 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.<br/>Napr.: <math>S_0 \rightarrow aS_0</math> alebo <math>S_0 \rightarrow a</math>.
 </ol>
@@ Riadok 23: / Riadok 23: @@
 | text = Možno si si všimol, že neterminálny symbol je zapísaný ako <math>S_0</math> namiesto iba <math>S</math>. 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).
 | emoji = ℹ️
-}}Platí, že jednotlivé typy gramatík sú hierarchiou podmnožín. Napríklad, {{Štítok|emoji=🧠|text=kontextové gramatiky|farba=goldenrod|farba_textu=black}} a {{Štítok|emoji=🔀|text=bezkontextové gramatiky|farba=mediumpurple|farba_textu=black}} spĺňajú kritériá pravidiel pre {{Štítok|emoji=➡️|text=regulárne gramatiky|farba=mediumseagreen|farba_textu=black}} (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á môžu byť zložitejšie.
+}}Platí, že jednotlivé typy gramatík sú hierarchiou podmnožín. Napríklad, {{Štítok|emoji=🧠|text=kontextové gramatiky|farba=goldenrod|farba_textu=black}} a {{Štítok|emoji=🔀|text=bezkontextové gramatiky|farba=mediumpurple|farba_textu=black}} spĺňajú kritériá pravidiel pre {{Štítok|emoji=➡️|text=regulárne gramatiky|farba=mediumseagreen|farba_textu=black}} (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 ==