Postać normalna Chomsky'ego

CFG jest w normalnej formie Chomsky'ego, jeśli produkcje są w następujących formach -

• A → a
• A → BC
• S → ε

gdzie A, B i C to nieterminale i a jest terminalem.

Algorytm konwersji do postaci normalnej Chomsky'ego -

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 - Wymień każdą produkcję A → B₁…B_n gdzie n > 2 z A → B₁C gdzie C → B₂ …B_n. Powtórz ten krok dla wszystkich produkcji, które mają dwa lub więcej symboli po prawej stronie.

Step 5 - Jeśli prawa strona jakiejkolwiek produkcji jest w formie A → aB gdzie a jest terminalem, a A, B są nieterminalne, wtedy produkcja jest zastępowana przez A → XB i X → a. Powtórz ten krok dla każdej produkcji, która jest w formieA → aB.

Problem

Zamień następujący CFG na CNF

S → ASA | aB, A → B | S, B → b | ε

Rozwiązanie

(1) Od S pojawia się w RHS, dodajemy nowy stan S₀ i S₀→S jest dodawany do zestawu produkcyjnego i staje się -

S ₀ → S, S → ASA | aB, A → B | S, B → b | ∈

(2) Teraz usuniemy zerowe produkcje -

B → ∈ i ​​A → ∈

Po usunięciu B → ε zbiór produkcyjny staje się -

S ₀ → S, S → ASA | aB | a, A → B | S | ∈, B → b

Po usunięciu A → ∈ zestaw produkcyjny staje się -

S ₀ → S, S → ASA | aB | a | AS | SA | S, A → B | S, B → b

(3) Teraz usuniemy produkcje jednostkowe.

Po usunięciu S → S zestaw produkcyjny staje się -

S ₀ → S, S → ASA | aB | a | AS | SA, A → B | S, B → b

Po usunięciu S ₀ → S zestaw produkcyjny staje się -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → B | S, B → b

Po usunięciu A → B zestaw produkcyjny staje się -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → S | b

B → b

Po usunięciu A → S zestaw produkcyjny staje się -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → b | ASA | aB | a | AS | SA, B → b

(4) Teraz dowiemy się więcej niż dwóch zmiennych w RHS

Tutaj S ₀ → ASA, S → ASA, A → ASA narusza dwa nie-zaciski w RHS

Dlatego zastosujemy krok 4 i krok 5, aby uzyskać następujący końcowy zestaw produkcyjny, który jest w CNF -

S ₀ → AX | aB | a | AS | SA

S → AX | aB | a | AS | SA

A → b | AX | aB | a | AS | SA

B → b

X → SA

(5)Musimy zmienić produkcje S ₀ → aB, S → aB, A → aB

A ostateczny zestaw produkcyjny to -

S ₀ → AX | YB | a | AS | SA

S → AX | YB | a | AS | SA

A → b A → b | AX | YB | a | AS | SA

B → b

X → SA

Y → a