3.1.8 Normální tvar podle Chomského

Definice (Normální tvar podle Chomského)

Normální tvar podle Chomského

Normální tvar podle Chomského (CNF) Každou bezkontextovou gramatiku lze převést do normálního tvaru podle Chomského. Bezkontextová gramatika je v normálním tvaru podle Chomského, pokud má pouze pravidla tvaru:

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

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

Jak převedeme bezkontextovou gramatiku do normálního tvaru podle Chomského?

Převod na normální tvar podle Chomského

1. Gramatiku nejprve převedeme na vlastní bez jednoduchých pravidel. Tedy odstraníme \(\varepsilon\)-pravidla, jednoduchá pravidla a pak zbytečné symboly.
2. Nyní budeme procházet jednotlivá pravidla a případně je upravovat do požadovaného tvaru:
   • Pravidla tvaru \(A \to a\), \(A \to BC\) (\(A, B, C \in N, a \in \Sigma\)) neupravujeme.
   • Všechny pravé strany pravidel, kde se vyskytuje terminál v kombinaci s dalšími symboly, upravíme tak, že terminál nahradíme novým neterminálem.
     • Příklad: \(A \to BaC\) (\(A, B, C \in N, a \in \Sigma\)) nahradíme pravidly: \(A \to Ba'C, a' \to a\), kde \(a'\) je nový neterminál.
   • Pokud je pravá strana tvořena více než dvěma neterminály, postupným „ukusováním“ vytvoříme posloupnost nových pravidel splňujících omezení dvou neterminálů na pravé straně.
     • Příklad: \(A \to ABCD\) (\(A, B, C, D \in N\)) nahradíme posloupností pravidel: \(A \to A\langle BCD \rangle\), \(\langle BCD \rangle \to B\langle CD \rangle\), \(\langle CD \rangle \to CD\), kde \(\langle BCD \rangle, \langle CD \rangle \in N\).