1.3 Gramatiky a jejich klasifikace

Gramatika

Gramatika je prostředek pro popis jazyků. Definujeme ji jako uspořádanou čtveřici \(G = (N, \Sigma, P, S)\), kde:

\(N\) je konečná neprázdná množina neterminálních symbolů (zkráceně neterminálů). Jedná se o pomocné proměnné reprezentující určité syntaktické celky.
\(\Sigma\) je konečná neprázdná abeceda symbolů, které nazýváme terminální symboly (zkráceně terminály). Jedná se o abecedu jazyka generovaného gramatikou. Platí, že \(N \cap \Sigma = \emptyset\).
\(P\) je konečná množina přepisovacích pravidel ve tvaru:

\[ \alpha A \beta \to \gamma \quad (\alpha, \beta, \gamma \in (N \cup \Sigma)^*, A \in N) \]

\(S \in N\) je počáteční (výchozí, startovací) neterminální symbol gramatiky.

Jak poznáme nezkracující gramatiku?

U nezkracující gramatiky musí všechna pravidla splňovat podmínku, že počet symbolů na levé straně pravidla je menší nebo roven počtu symbolů na pravé straně daného pravidla.

Jedinou přípustnou výjimkou je pravidlo \(S \to \varepsilon\), a to jen za předpokladu, že se počáteční neterminál \(S\) neobjevuje na pravé straně žádného pravidla. V nezkracující gramatice tak žádná jiná \(\varepsilon\)-pravidla nemohou existovat.

Chomského klasifikace gramatik

Chomského klasifikace gramatik vymezuje na základě tvaru přepisovacích pravidel následující čtyři typy gramatik:

Regulární gramatika (RG, typ 3)

Regulární gramatika

Má pravidla tvaru:

\[ A \to a \quad \text{nebo} \quad A \to aB \quad (a \in \Sigma, A, B \in N) \]

Jedinou povolenou výjimkou z těchto pravidel je pravidlo \(S \to \varepsilon\). Toto pravidlo se v regulární gramatice může vyskytnout za předpokladu, že počáteční neterminál \(S\) se nevyskytuje na pravé straně žádného pravidla.

Vlastnost RG

Regulární gramatika je nezkracující. Obráceně toto tvrzení neplatí. Tedy ne každá nezkracující gramatika je regulární.

Bezkontextová gramatika (BG, typ 2)

Bezkontextová gramatika

Má pravidla tvaru:

\[ A \to \alpha \quad (\alpha \in (N \cup \Sigma)^*, A \in N) \]

Kontextová gramatika (KG, typ 1)

Kontextová gramatika

Má pravidla tvaru:

\[ \gamma A \delta \to \gamma \alpha \delta \quad (\gamma, \delta \in (N \cup \Sigma)^*, A \in N, \alpha \in (N \cup \Sigma)^+) \]

Jedinou povolenou výjimkou z těchto pravidel je pravidlo \(S \to \varepsilon\). Toto pravidlo se v kontextové gramatice může vyskytnout za předpokladu, že počáteční neterminál \(S\) se nevyskytuje na pravé straně žádného pravidla.

Vlastnost KG

Kontextová gramatika je nezkracující. Obráceně toto tvrzení neplatí. Tedy ne každá nezkracující gramatika je kontextová.

Neomezená gramatika (NG, typ 0)

Neomezená gramatika

Má pravidla tvaru:

\[ \alpha A \beta \to \gamma \quad (\alpha, \beta, \gamma \in (N \cup \Sigma)^*, A \in N) \]

Z Chomského klasifikace gramatik plyne následující pozorování:

Regulární gramatika je vždy zároveň bezkontextová, kontextová a neomezená.
Bezkontextová gramatika není vždy zároveň kontextová, záleží na pravidlech dané gramatiky, neboť bezkontextová gramatika může být zkracující, zatímco kontextová nikoliv. Bezkontextová gramatika je však vždy zároveň neomezená.
Kontextová gramatika je vždy zároveň neomezená.

Postup při návrhu gramatiky pro zadaný jazyk

Jak postupujeme při návrhu gramatiky pro zadaný jazyk?

Máme za úkol navrhnout gramatiku konkrétního typu? Například bezkontextovou? Ujasněme si, jak vypadají pravidla pro požadovaný typ gramatiky.
Promysleme si, jak vypadají řetězce z jazyka: Jak vypadá nejkratší řetězec z jazyka? Nezapomeňme na \(\varepsilon\). Musí se nějaký symbol vyskytovat povinně ve všech řetězcích? Kolikrát? Vypišme si konkrétní příklady. Jaký vztah mezi sebou mají jednotlivé řetězce z jazyka?
Lze jazyk rozdělit na sjednocení jednodušších jazyků? Udělejme to. Pro spojení gramatik poté využijeme standardní algoritmus.
Pokud je to vhodné, přidáme jednotlivým neterminálům sémantický význam.
Nezávislé části řetězců z jazyka generujeme odděleně pomocí různých neterminálních symbolů. Předejdeme tím nechtěnému pomíchání symbolů v generovaných řetězcích. Případnému nechtěnému pomíchání symbolů v generovaných řetězcích předejme též tím, že si pro vybrané řetězce z jazyka nakreslíme derivační strom.

Postup při klasifikaci „neznámého“ jazyka L

Jak postupujeme při klasifikaci „neznámého“ jazyka L?

Lze jazyk \(L\) přijmout konečným automatem, generovat regulární gramatikou nebo popsat regulárním výrazem? Pokud ano, jazyk \(L\) je regulární.
Lze jazyk \(L\) přijmout zásobníkovým automatem nebo generovat bezkontextovou gramatikou? Pokud ano, jazyk \(L\) je bezkontextový. Není však zároveň regulární? (viz krok 1) Pokud není, musíme toto tvrzení formálně dokázat (např. pomocí pumping lemmatu, Myhillovy-Nerodovy věty nebo uzávěrových vlastností).
Lze jazyk \(L\) přijmout lineárně omezeným Turingovým strojem, generovat kontextovou nebo nezkracující gramatikou? Pokud ano, jazyk \(L\) je kontextový. Není však zároveň bezkontextový (či dokonce regulární)? (viz kroky 1 a 2) Pokud není, musíme toto tvrzení formálně dokázat (např. pomocí pumping lemmatu pro bezkontextové jazyky nebo uzávěrových vlastností). Takový formální důkaz je však již nad rámec tohoto textu.
Lze jazyk \(L\) přijmout Turingovým strojem nebo generovat neomezenou gramatikou? Pokud ano, jazyk \(L\) je rekurzivně spočetný. Není však zároveň kontextový (či dokonce bezkontextový, regulární)? (viz kroky 1, 2 a 3) Pokud není, musíme toto tvrzení formálně dokázat (toto už je často těžší úkol, který je však nad rámec tohoto textu).