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