Uproszczenie CFG

W CFG może się zdarzyć, że wszystkie reguły produkcji i symbole nie są potrzebne do wyprowadzenia łańcuchów. Poza tym mogą istnieć produkcje zerowe i jednostkowe. Eliminacja tych produkcji i symboli nazywa sięsimplification of CFGs. Uproszczenie składa się zasadniczo z następujących kroków -

Redukcja CFG
Usunięcie produkcji jednostkowej
Usunięcie Null Productions

Redukcja CFG

CFG są redukowane w dwóch fazach -

Phase 1 - wyprowadzenie równoważnej gramatyki, G’z CFG, G, tak że każda zmienna wyprowadza jakiś ciąg terminala.

Derivation Procedure -

Krok 1 - Uwzględnij wszystkie symbole, W₁, które wyprowadzają jakiś terminal i inicjalizują i=1.

Krok 2 - Uwzględnij wszystkie symbole, W_i+1, które pochodzą W_i.

Krok 3 - Przyrost i i powtórz krok 2, aż W_i+1 = W_i.

Krok 4 - Uwzględnij wszystkie reguły produkcji, które mają W_i w tym.

Phase 2 - wyprowadzenie równoważnej gramatyki, G”z CFG, G’tak, że każdy symbol pojawia się w formie zdaniowej.

Derivation Procedure -

Krok 1 - Uwzględnij symbol początkowy w Y₁ i zainicjuj i = 1.

Krok 2 - Uwzględnij wszystkie symbole, Y_i+1, z którego można wywodzić Y_i i uwzględnij wszystkie zastosowane reguły produkcji.

Krok 3 - Przyrost i i powtórz krok 2, aż Y_i+1 = Y_i.

Problem

Znajdź zredukowany odpowiednik gramatyki do gramatyki G, mający reguły produkcji, P: S → AC | B, A → a, C → c | BC, E → aA | mi

Rozwiązanie

Phase 1 -

T = {a, c, e}

W ₁ = {A, C, E} z reguł A → a, C → c i E → aA

W ₂ = {A, C, E} U {S} z reguły S → AC

W ₃ = {A, C, E, S} U ∅

Ponieważ W ₂ = W ₃ , możemy wyprowadzić G 'jako -

G '= {{A, C, E, S}, {a, c, e}, P, {S}}

gdzie P: S → AC, A → a, C → c, E → aA | mi

Phase 2 -

Y ₁ = {S}

Y ₂ = {S, A, C} z reguły S → AC

Y ₃ = {S, A, C, a, c} z reguł A → a i C → c

Y ₄ = {S, A, C, a, c}

Ponieważ Y ₃ = Y ₄ , możemy wyprowadzić G ”jako -

G ”= {{A, C, S}, {a, c}, P, {S}}

gdzie P: S → AC, A → a, C → c

Usunięcie produkcji jednostkowej

Dowolna reguła produkcji w postaci A → B, w której A, B ∈ jest wywoływana unit production..

Procedura usuwania -

Step 1 - Aby usunąć A → Bdodaj produkcję A → x do reguły gramatyki kiedykolwiek B → xwystępuje w gramatyce. [x ∈ Terminal, x może mieć wartość Null]

Step 2 - Usuń A → B z gramatyki.

Step 3 - Powtarzaj od kroku 1, aż wszystkie produkcje jednostkowe zostaną usunięte.

Problem

Usuń produkcję jednostkową z następujących -

S → XY, X → a, Y → Z | b, Z → M, M → N, N → a

Solution -

W gramatyce są 3 produkcje jednostkowe -

Y → Z, Z → M i M → N

At first, we will remove M → N.

Jako N → a dodajemy M → a, a M → N jest usuwane.

Zestaw produkcyjny staje się

S → XY, X → a, Y → Z | b, Z → M, M → a, N → a

Now we will remove Z → M.

Jako M → a dodajemy Z → a, a Z → M jest usuwane.

Zestaw produkcyjny staje się

S → XY, X → a, Y → Z | b, Z → a, M → a, N → a

Now we will remove Y → Z.

Jako Z → a dodajemy Y → a, a Y → Z jest usuwane.

Zestaw produkcyjny staje się

S → XY, X → a, Y → a | b, Z → a, M → a, N → a

Teraz Z, M i N są nieosiągalne, dlatego możemy je usunąć.

Ostateczna wersja CFG jest bez produkcji jednostkowej -

S → XY, X → a, Y → a | b

Usunięcie Null Productions

W CFG: symbol nieterminalny ‘A’ jest zmienną dopuszczającą wartość null, jeśli istnieje produkcja A → ε lub istnieje wyprowadzenie, które zaczyna się od A i ostatecznie kończy się

ε: A → .......… → ε

Procedura usuwania

Step 1 - Znajdź zmienne nieterminalne dopuszczające wartość null, które wyprowadzają ε.

Step 2 - Do każdej produkcji A → a, skonstruuj wszystkie produkcje A → x gdzie x jest uzyskiwany z ‘a’ usuwając jeden lub wiele nieterminali z kroku 1.

Step 3 - Połącz oryginalne produkcje z wynikiem kroku 2 i usuń ε - productions.

Problem

Usuń zerową produkcję z następujących -

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

Solution -

Istnieją dwie zmienne dopuszczające wartość null - A i B

At first, we will remove B → ε.

Po usunięciu B → ε, zestaw produkcyjny staje się -

S → ASA | aB | b | a, A ε B | b | & epsilon, B → b

Now we will remove A → ε.

Po usunięciu A → ε, zestaw produkcyjny staje się -

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