01 Gramatika

Last updated Nov 9, 2022

$$ \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}} $$

# Gramatika

Čtveřice $G = (N, \Sigma, P, S)$, kde:
- $N$ - konečná množina neterminálů ^a5e0fd
- $\Sigma$ též $T$ - konečná množina terminálů ^7dbe37
- $P$ - množina přepisovacích pravidel
- $S$ - počáteční symbol (neterminál) gramatiky (též větný/startovací symbol)
Je to formalismus pro generování jazyka

Pozor! $G$ je uspořádaná čtveřice $(\space)$, není to množina ${\space}$ !

Cílem gramatiky je, aby generovala nějaký jazyk

Lze zapsat také:

Výčtem: $L_1 = {ab, ac, cb}$
Matematicky: $L_2 = {a^n b^n : n \ge 0} = {ab, aabb, aaabbb, aaaabbbb, \dots}$

Jedné gramatice je vždy přiřazen pouze jeden jazyk, ale jeden jazyk může mít nekonečně mnoho (ekvivalentních) gramatik.

# Příklad gramatiky

Gramatika $G_{1}= ({A,S}, {0,1}, P, S)$ kde $P:$

$S \rightarrow 0A$
$A \rightarrow 1A$
$A \rightarrow 0$

# Definice pojmů

# Derivace

Postup, při kterém se na řetězec uplatní konečný počet (žádné, jedno nebo více) přepsání
Posloupnost “přepisů” (větných forem) dle pravidel
$\alpha \Rightarrow^{k} \beta\enspace$ = Derivace řetězce $\beta$ z řetězce $\alpha$, která má délku $k$ v gramatice (tj. existuje posloupnost řetězců) $\Rightarrow^{+}\enspace$ = Tranzitivní uzávěr (derivuje po nenulovém počtu kroků) $\Rightarrow^{*}\enspace$ = Tranzitivní a reflexivní uzávěr (derivuje po libovolném počtu kroků)
Přímá derivace - pouze 1 krok derivace
Může být levá či pravá či jiná derivace

# Větná forma

Řetězec nazveme větnou formou v gramatice $G$, jestliže $S\Rightarrow^{}\alpha, \alpha \in (N \cup \Sigma)^$ (tedy ze startovního symbolu $S$ se lze přepsat do takového řetězce $\alpha$, který je tvořen libovolným počtem symbolů terminálů i neterminálů)
Větná forma v $G$, která neobsahuje žádné $N$ symboly se nazývá věta generovaná gramatikou $G$ ^veta