Chomského hierarchia jazykov: Rozdiel medzi revíziami

Verzia z 19:10, 19. október 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.

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

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ť). 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. Používajú sa najčastejšie pre popis syntaxe programovacích jazykov. Napr.: $a S_{0} b \to a a b$
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 ihneď nasleduje 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.

Referencie

« Úvod do formálnych jazykov

Chomského hierarchia jazykov »

@@ Riadok 10: / Riadok 10: @@
 <ol start="0">
 <li>typ: {{Štítok|emoji=🔃|text=rekurzívne enumerovateľné gramatiky|farba=hotpink|farba_textu=black}} - 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ť).
-<li>Napr.: <math>aabbaa \rightarrow aS_0aS_0df</math> alebo <math>S_0livka \rightarrow aS_0dS_0fdaf</math>
+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}} - ľ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.
-<li>Používajú sa najčastejšie pre popis syntaxe programovacích jazykov.
+<li>typ: {{Štítok|emoji=🧠|text=kontextové gramatiky|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. Používajú sa najčastejšie pre popis syntaxe programovacích jazykov.
-<li>Napr.: <math>aS_0b \rightarrow aab</math>
+Napr.: <math>aS_0b \rightarrow aab</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.
-<li>Napr.: <math>S_0 \rightarrow aS_0bcS_0a</math>
+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.
-<li>Napr.: <math>S_0 \rightarrow aS_0</math> alebo <math>S_0 \rightarrow a</math>
+Napr.: <math>S_0 \rightarrow aS_0</math> alebo <math>S_0 \rightarrow a</math>
 </ol>