01 Klasifikace gramatik a jazyků
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
Klasifikace gramatik a jazyků
- Noam Chomsky
- Chomskyho klasifikace gramatik
- Dělí jazyky a gramatiky do tříd
# Klasifikace jazyků
| Formální jazyk | Gramatika | Model výpočtu (automat) |
|---|---|---|
| 0. rekurzivně spočetné | neomezené pravidlo | Turingův stroj |
| 1. kontextové | pravidlo má na obou stranách stejný kontext (např. $\gamma A \delta \Rightarrow \gamma B \delta$) | lineární automat (TM s omezenou velikostí pásky) |
| 2. bezkontextové | A -> $\alpha$ (vlevo neterminál, na pravé straně může být cokoliv) | zásobníkový automat |
| 3. regulární* | regulární | konečný automat |
*každá regulární je zároveň i bezkontextová, ale ne obráceně
Minimální deterministický konečný automat - nejefektivnější model výpočtu pro daný problém
Pumpování = rekurzivně vytvoření libovolně dlouhé posloupnosti
# Klasifikace gramatik
# Regulární gramatiky (RG)
- Na levé straně max. 1 $N$, na pravé pouze $T$ nebo $TN$
- $N \rightarrow T\space \vert \space TN$
- $S \rightarrow \varepsilon \enspace$ a zároveň $S$ není na pravé straně žádného z pravidel
Pozorování
- Prázdný jazyk $L(G)={}$ lze generovat RG, tedy prázdný jazyk patří do všech [tříd](None#Klasifikace jazyků) jazyků
- Pro každý konečný jazyk lze vyrobit regulární gramatiku, tedy každý konečný jazyk je i regulární
# Bezkontextové gramatiky (BG)
- $N \rightarrow (N \cup T)^*$
- $(N \cup T)^*$ = cokoliv = libovolně dlouhý řetězec složený z terminálů i neterminálů
Pozorování
- Derivační strom pouze pro BG, protože vlevo nesmí být víc symbolů
# Kontextové gramatiky (KG)
- $\alpha \space N \space \beta \rightarrow \alpha \space (N \cup T)^{+} \space \beta$
- $\alpha, \beta \in (N \cup T)^*$ = tzv. kontext, tedy $\alpha$ i $\beta$ může být cokoliv
- Neumí vygenerovat prázdný řetězec $\varepsilon$
- $S \rightarrow \varepsilon \enspace$ a zároveň $S$ není na pravé straně žádného z pravidel
# Neomezené gramatiky (NG)
- $(N \cup T)^{}\space N \space (N \cup T)^ \rightarrow (N \cup T)^*$
Možnosti klasifikací gramatik
Gramatiky mohou splňovat více klasifikací najednou, ale jen tyto možnosti z toho vychází jako validní:
- NG
- BG, NG
- KG, NG
- BG, KG, NG
- RG, BG, KG, NG
Pozorování
- Gramatika, ve které existují pouze derivace nekonečné délky, generuje prázdný jazyk