Skip to content

3.1.6 Odstranění zbytečných symbolů

Definice (Nedostupný symbol)

Nedostupný symbol

Nedostupný symbol je takový symbol \(X\) (terminál nebo neterminál) v gramatice, který se neobjevuje v žádné větné formě. Tedy neexistuje derivace \(S \Rightarrow^* uXv\), kde \(S\) je počáteční neterminál a \(u, v \in (N \cup \Sigma)^*\).

Definice (Zbytečný symbol)

Zbytečný symbol

Zbytečný symbol je takový symbol \(X\) (terminál nebo neterminál) v gramatice, který je nedostupný nebo jehož výskyt v rámci větné formy způsobí, že žádnou derivací nelze tuto větnou formu přeměnit na větu. Tedy neexistuje derivace \(S \Rightarrow^* uXv \Rightarrow^* uwv\), kde \(S\) je počáteční neterminál a \(u, v, w \in \Sigma^*\).

Pozorování

Každý nedostupný symbol je zbytečný. Obráceně toto tvrzení neplatí. Tedy ne každý zbytečný symbol je nedostupný.

Definice (Redukovaná a vlastní bezkontextová gramatika)

Redukovaná a vlastní gramatika

  • Redukovaná bezkontextová gramatika je bezkontextová gramatika bez zbytečných symbolů.
  • Vlastní bezkontextová gramatika je bez cyklů, bez \(\varepsilon\)-pravidel a bez zbytečných symbolů.

Jak z bezkontextové gramatiky odstraníme zbytečné symboly?

Algoritmus odstranění zbytečných symbolů

1. Odstranění neukončitelných neterminálů

Iterativně zkonstruujeme množinu „ukončitelných“ neterminálů \(N_t\) (tj. neterminálů, které generují nějaký řetězec):

  • Inicializace:
\[N_t^0 = \emptyset\]
  • První krok:
\[N_t^1 = N_t^0 \cup \{ \text{všechny neterminály, které mají na pravé straně alespoň jednoho z pravidel pouze posloupnost terminálních symbolů či } \varepsilon \}\]
  • i-tý krok:
\[N_t^i = N_t^{i-1} \cup \{ \text{všechny neterminály, které mají na pravé straně alespoň jednoho z pravidel pouze terminální symboly v kombinaci s neterminály z předchozí množiny } N_t^{i-1} \}\]
  • Konec: Množina \(N_t\) je hotová, pokud další krok již do množiny nepřidá žádný nový neterminál.

Všechny neterminály, které nejsou v množině \(N_t\), z gramatiky odstraníme.

2. Odstranění nedostupných symbolů

Iterativně zkonstruujeme množinu dostupných symbolů \(V\) (lze provést až po ukončení předchozích kroků):

  • Inicializace:
\[V^0 = \{S\}\]

(\(S\) je počáteční neterminální symbol)

  • První krok:
\[V^1 = V^0 \cup \{ \text{všechny terminály a neterminály vyskytující se na pravé straně pravidel pro neterminál } S \}\]
  • i-tý krok:
\[V^i = V^{i-1} \cup \{ \text{všechny terminály a neterminály vyskytující se na pravé straně pravidel pro neterminály z předchozí množiny } V^{i-1} \}\]
  • Konec: Množina \(V\) je hotová, pokud další krok již do množiny nepřidá žádný nový (ne)terminál.

Všechny neterminály a terminály, které nejsou v množině \(V\), z gramatiky odstraníme.