Skip to content

3.1.5 Odstranění jednoduchých pravidel

Definice (Jednoduché pravidlo)

Jednoduché pravidlo

Jednoduché pravidlo je pravidlo tvaru \(A \to B\), kde \(A\) a \(B\) jsou libovolné neterminály. Intuitivně nám toto pravidlo říká, že neterminál \(A\) na levé straně se „umí chovat stejně“ jako neterminál \(B\) na pravé straně.

Definice (Bezkontextová gramatika bez cyklů)

Bezkontextová gramatika bez cyklů

Bezkontextová gramatika bez cyklů je taková bezkontextová gramatika, kde není pro žádný neterminál možná derivace \(A \Rightarrow^+ A\).

Platí, že pokud je gramatika bez jednoduchých a \(\varepsilon\)-pravidel, poté je bez cyklů (obráceně platit nemusí).

Jak z bezkontextové gramatiky odstraníme jednoduchá pravidla?

Algoritmus odstranění jednoduchých pravidel

1. Konstrukce množin \(N_A\)

Iterativně sestavíme množinu \(N_A\) pro každý neterminál \(A \in N\). Jedná se o takový „uzávěr“ přes jednoduchá pravidla. Množinu \(N_A\) sestavíme následovně:

  • Inicializace:
\[N_A^0 = \{A\}\]
  • První krok:
\[N_A^1 = N_A^0 \cup \{ \text{všechny neterminály, které spolu s neterminálem } A \text{ na levé straně tvoří jednoduché pravidlo} \}\]
  • i-tý krok:
\[N_A^i = N_A^{i-1} \cup \{ \text{všechny neterminály, které spolu s neterminálem z množiny } N_A^{i-1} \text{ na levé straně tvoří jednoduché pravidlo} \}\]
  • Konec: Množina \(N_A\) je hotová, pokud další krok již do množiny nepřidá žádný nový neterminál.

2. Úprava pravidel

Pokud máme vyrobenou množinu \(N_A\) pro každý neterminál \(A \in N\), upravíme pravidla gramatiky následovně:

  • Z gramatiky nejprve odstraníme všechna jednoduchá pravidla.
  • Nyní budeme procházet jednotlivé množiny a upravovat odpovídající pravidla. Množina \(N_A\) nám intuitivně říká, že neterminál \(A\) se „chová“ jako neterminály uvnitř této množiny. Všechny pravé strany pravidel pro neterminály z množiny \(N_A\) tedy nakopírujeme k neterminálu \(A\).