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, W1, które wyprowadzają jakiś terminal i inicjalizują i=1.

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

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

Krok 4 - Uwzględnij wszystkie reguły produkcji, które mają Wi 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 Y1 i zainicjuj i = 1.

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

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

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 1 = {A, C, E} z reguł A → a, C → c i E → aA

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

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

Ponieważ W 2 = W 3 , 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 1 = {S}

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

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

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

Ponieważ Y 3 = Y 4 , 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

To jest ostateczny zestaw produkcyjny bez przejścia zerowego.