5.1 Kontextové gramatiky

Kontextová gramatika

Kontextová gramatika je uspořádaná čtveřice \(G = (N, \Sigma, P, S)\), kde pravidla \(P\) jsou 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.

Pozorování

Kontextová gramatika je vždy zároveň neomezená.

Definice (Nezkracující gramatika)

Nezkracující gramatika

Nezkracující gramatika je taková gramatika, kde pro každé pravidlo platí, že počet symbolů na levé straně je menší nebo roven počtu symbolů na pravé straně.

Díky tomu v nezkracující gramatice nemohou existovat \(\varepsilon\)-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.

Vztah kontextových a nezkracujících gramatik

Každá kontextová gramatika je nezkracující.

Každá nezkracující gramatika může být na kontextovou gramatiku převedena.