Skip to content

3.1.4 Odstranění ε-pravidel

Definice (\(\varepsilon\)-pravidlo)

\(\varepsilon\)-pravidlo

\(\varepsilon\)-pravidlo je pravidlo tvaru \(A \to \varepsilon\), kde \(A\) je libovolný neterminál. Intuitivně nám toto pravidlo říká, že daný neterminál může v průběhu derivace kdykoli zmizet.

Definice (Bezkontextová gramatika bez \(\varepsilon\)-pravidel)

Bezkontextová gramatika bez \(\varepsilon\)-pravidel

Bezkontextová gramatika bez \(\varepsilon\)-pravidel je taková bezkontextová gramatika, kde:

  • neexistuje žádné \(\varepsilon\)-pravidlo,
  • nebo zde existuje pouze jediné: \(S \to \varepsilon\), kde \(S\) je počáteční neterminál a \(S\) se nevyskytuje na pravé straně žádného z pravidel gramatiky.

Jak z bezkontextové gramatiky odstraníme \(\varepsilon\)-pravidla?

Algoritmus odstranění \(\varepsilon\)-pravidel

1. Konstrukce množiny \(N_\varepsilon\)

Iterativně sestavíme množinu \(N_\varepsilon\) obsahující všechny neterminály, které lze přímo či nepřímo přepsat na prázdný řetězec:

  • Inicializace:
\[N_\varepsilon^0 = \emptyset\]
  • První krok:
\[N_\varepsilon^1 = N_\varepsilon^0 \cup \{ \text{všechny neterminály, které mají v gramatice } \varepsilon\text{-pravidlo} \}\]
  • i-tý krok:
\[N_\varepsilon^i = N_\varepsilon^{i-1} \cup \{ \text{všechny neterminály, které mají na pravé straně alespoň jednoho z pravidel libovolnou kombinaci neterminálů z předchozí množiny } N_\varepsilon^{i-1} \}\]

(Pozor, bez terminálních symbolů a neterminálů, které nejsou v množině \(N_\varepsilon^{i-1}\)).

  • Konec: Množina \(N_\varepsilon\) je hotová, pokud další krok již do množiny nepřidá žádný nový neterminál.

2. Úprava pravidel

Pomocí výsledné množiny \(N_\varepsilon\) upravíme pravidla v gramatice:

  • Z gramatiky nejprve odstraníme všechna \(\varepsilon\)-pravidla. Pokud ovšem \(S \in N_\varepsilon\) (kde \(S\) je počáteční neterminál), poté pravidlo \(S \to \varepsilon\):
    • v gramatice ponecháme (pouze pokud se \(S\) nevyskytuje na pravé straně),
    • jinak toto pravidlo odstraníme, ale do gramatiky přidáme nový počáteční neterminál \(S'\) s pravidly \(S' \to S \mid \varepsilon\).
  • Projdeme jednotlivá pravidla v gramatice a pokud se na pravé straně vyskytuje nějaký neterminál z množiny \(N_\varepsilon\), poté do gramatiky přidáme kopii tohoto pravidla, která však nebude obsahovat příslušný neterminál z množiny \(N_\varepsilon\).
    • Příklad: \(A \to aBc\) a \(B \in N_\varepsilon\), poté pravidla upravíme na \(A \to aBc \mid ac\).

Pozor na kombinace

Pokud se na pravé straně pravidla vyskytuje více než jeden neterminál z množiny \(N_\varepsilon\), je nutné přidat pravidla se všemi možnými kombinacemi bez těchto neterminálů na pravé straně.

Pokud se během přidávání nových pravidel dostaneme do situace, kdy bychom do gramatiky měli vložit \(\varepsilon\)-pravidlo, do gramatiky jej nepřidáme. (Například: \(A \to BC\), kde \(B, C \in N_\varepsilon\), upravíme pouze na \(A \to BC \mid B \mid C\) a pravidlo \(A \to \varepsilon\) nepřidáme).