Normalna forma Greibacha
CFG jest w normalnej formie Greibach, jeśli produkcje są w następujących formach -
A → b
A → bD 1 … D n
S → ε
gdzie A, D 1 , ...., D n to nieterminale, a b to terminal.
Algorytm konwersji CFG do postaci normalnej Greibach
Step 1 - Jeśli symbol startu S występuje po prawej stronie, utwórz nowy symbol początku S’ i nową produkcję S’ → S.
Step 2- Usuń zerowe produkcje. (Korzystanie z algorytmu usuwania Null Production omówionego wcześniej)
Step 3- Usuń produkcje jednostkowe. (Korzystanie z omówionego wcześniej algorytmu usuwania produkcji jednostkowej)
Step 4 - Usuń całą bezpośrednią i pośrednią lewostronną rekursję.
Step 5 - Wykonuj odpowiednie podstawienia produkcji, aby zamienić je na właściwą formę GNF.
Problem
Zamień następujący CFG na CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
Rozwiązanie
Tutaj, Snie pojawia się po prawej stronie żadnej produkcji i nie ma produkcji jednostkowej lub zerowej w zestawie reguł produkcji. Możemy więc pominąć krok 1 do kroku 3.
Step 4
Teraz po wymianie
X w S → XY | Xo | p
z
mX | m
otrzymujemy
S → mXY | mY | mXo | mo | p.
A po wymianie
X w Y → X n | o
prawą stroną
X → mX | m
otrzymujemy
Y → mXn | mn | o.
Do zestawu produkcyjnego dodano dwie nowe produkcje O → o i P → p, a następnie doszliśmy do końcowego GNF w następujący sposób -
S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O → o
P → p