Chomského hierarchia jazykov: Rozdiel medzi revíziami

Aktuálna revízia z 10:54, 3. január 2025

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í.

Vizuálne znázornenie Chomského hierarchie — Chomského hierarchia.

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: 🔃 frázové jazyky (podmnožiny: rekurzívne a rekurzívne vyčísliteľné jazyky) - 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é jazyky ľ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é jazyky - ľ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 jazyky - 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é jazyky a 🔀 bezkontextové jazyky spĺňajú kritériá pravidiel pre ➡️ regulárne jazyky (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).

« Gramatika vo formálnych jazykoch

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

@@ Riadok 4: / Riadok 4: @@
 == 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 [https://chomsky.info/wp-content/uploads/195609-.pdf 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.
+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í.
+[[Súbor:Chomskeho hierarchie.svg|alt=Vizuálne znázornenie Chomského hierarchie|náhľad|284x284bod|Chomského hierarchia.]]
+V roku 1956 Noam Chomsky položil základy pre túto hierarchiu [https://chomsky.info/wp-content/uploads/195609-.pdf 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:
@@ Riadok 10: / Riadok 13: @@
 <ol start="0">
-<li>typ: {{Štítok|emoji=🔃|text=frázové gramatiky|farba=hotpink|farba_textu=black}} (''<u>rekurzívne vyčísliteľné jazyky</u>'') - 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).<br/>Napr.: <math>aabbaa \rightarrow aS_0aS_0df</math> alebo <math>S_0livka \rightarrow aS_0dS_0fdaf</math>.
+<li>typ: {{Štítok|emoji=🔃|text=frázové jazyky|farba=hotpink|farba_textu=black}} (podmnožiny: ''<u>rekurzívne a rekurzívne vyčísliteľné jazyky</u>'') - 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).<br/>Napr.: <math>aabbaa \rightarrow aS_0aS_0df</math> alebo <math>S_0livka \rightarrow aS_0dS_0fdaf</math>.
-<li>typ: {{Štítok|emoji=🧠|text=kontextové gramatiky|farba=goldenrod|farba_textu=black}} (''r<u>ekurzívne jazyky</u>'') - ľ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: <math>\color{red} abba \rightarrow b</math>, <math>\color{red} abba \rightarrow \epsilon</math>). Tieto typy gramatík sa používajú najčastejšie pre popis syntaxe programovacích jazykov.<br/>Napr.: <math>aS_0b \rightarrow aab</math> alebo <math>aS_0b \rightarrow bS_0a</math>.
+<li>typ: {{Štítok|emoji=🧠|text=kontextové jazyky|farba=goldenrod|farba_textu=black}} ľ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: <math>\color{red} abba \rightarrow b</math>, <math>\color{red} abba \rightarrow \epsilon</math>). Tieto typy gramatík sa používajú najčastejšie pre popis syntaxe programovacích jazykov.<br/>Napr.: <math>aS_0b \rightarrow aab</math> alebo <math>aS_0b \rightarrow bS_0a</math>.
-<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=bezkontextové jazyky|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 nasleduje ihneď 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 jazyky|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 26: @@
 | 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á tým pádom môžu byť zložitejšie (viac rekurzie, a podobne).{{Téma|Oblast=Kategória:Formálne jazyky a automaty|Poradie=30}}
+}}Platí, že jednotlivé typy gramatík sú hierarchiou podmnožín. Napríklad, {{Štítok|emoji=🧠|text=kontextové jazyky|farba=goldenrod|farba_textu=black}} a {{Štítok|emoji=🔀|text=bezkontextové jazyky|farba=mediumpurple|farba_textu=black}} spĺňajú kritériá pravidiel pre {{Štítok|emoji=➡️|text=regulárne jazyky|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).{{Téma|Oblast=Kategória:Formálne jazyky a automaty|Poradie=30}}
 [[Kategória:Formálne jazyky a automaty]]