Języki, automaty i obliczenia/Wykład 9: Języki bezkontekstowe i ich gramatyki

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

W tym wykładzie rozpoczniemy omawianie drugiej w hierarchii Chomsky'ego rodziny języków formalnych, a mianowicie języków bezkontekstowych. Przedstawimy gramatyki bezkontekstowe i ich prostsze, a zarazem równoważne, postacie.

Gramatyki języków bezkontekstowych

Języki typu (2), zwane językami bezkontekstowymi, są rodziną szerszą niż omówione wcześniej języki regularne. Jak stwierdziliśmy w poprzednich wykładach gramatyki regularne generują poprawne napisy poprzez ciąg przepisywań metodą "od lewej do prawej". Natomiast gramatyki bezkontekstowe, zwane w lingwistyce gramatykami bezkontekstowych struktur frazowych, generują poprawne napisy poprzez sekwencję przepisywań, która ma strukturę drzewa. Ze względu na tę właśnie strukturę, gramatyki bezkontekstowe nadają się bardzo dobrze do opisu syntaktyki języków programowania. Z tego też powodu nastąpił szybki rozwój teorii gramatyk i języków bezkontekstowych.

Na wstępie przypomnijmy, że każda produkcja jakiejkolwiek gramatyki bezkontekstowej ma postać lub , gdzie . Często korzystać będziemy z możliwości przedstawienia graficznego takiej produkcji. Mianowicie każdej produkcji odpowiada etykietowane drzewo z wyróżnionym wierzchołkiem początkowym.

Rysunek 1

Drzewo odpowiadające pojedynczej produkcji z gramatyki nazywane jest drzewem elementarnym. Mając dowolne wyprowadzenie w gramatyce , można przedstawić je graficznie w postaci etykietowanego drzewa. Niech

będzie wyprowadzeniem słowa w gramatyce . Drzewo reprezentujące to wyprowadzenie powstaje z połączenia drzew elementarnych odpowiadających pojedynczym produkcjom występującym w wyprowadzeniu słowa w taki sposób, aby spełnić poniższe warunki:

  • wierzchołek początkowy jest etykietowany przez ,
  • każdy wierzchołek nie będący liściem, czyli wierzchołkiem maksymalnym w drzewie, jest oznaczony przez elementy z ,
  • jeśli jest symbolem nieterminalnym występującym w słowie w wyprowadzeniu , to bezpośrednie następniki wierzchołka etykietowanego przez są oznaczone przez symbole (porządek od lewej do prawej), gdzie i ta

właśnie produkcja została wykorzystana w bezpośrednim wyprowadzeniu , to znaczy we fragmencie wyprowadzenia

  • wierzchołki maksymalne drzewa (ciąg liści "od lewej strony") to słowo , przy czym, jeśli wszystkie wierzchołki maksymalne są etykietowane przez 1, to , a w przeciwnym razie wierzchołki oznaczone przez pomijamy.

Przykład 1.1

Niech , gdzie

Wówczas wyprowadzeniu
odpowiada drzewo
Rysunek 2

W poniższym przykładzie, jak i w dalszych wykładach symbolem oznaczamy kopię alfabetu , o której zakładać będziemy, że jest to zbiór rozłączny z oryginalnym alfabetem.

Przykład 1.2

  1. Język Dycka.
    Określamy bezkontekstową gramatykę , w której
    .
    Język generowany przez tę gramatykę, nazywany językiem Dycka, oznaczany jest przez . Język Dycka zwany jest też językiem "poprawnych nawiasów" przy interpretacji symboli jako lewego i prawego nawiasu.
    Język Dycka można zdefiniować także dla alfabetu mającego więcej niż dwa symbole. Do zbioru praw gramatyki wprowadza się wszystkie możliwe prawa postaci . W tym przypadku dla języka Dycka używa się oznaczenia , aby zaznaczyć liczbę elementów alfabetu .
  2. Język Łukasiewicza.
    Język Łukasiewicza jest generowany przez gramatykę bezkontekstową , gdzie , , oraz . Język Łukasiewicza jest więc zbiorem

    Używając tego języka, możemy zapisywać wyrażenia algebraiczne bez użycia nawiasów (notacja polska, prefiksowa), interpretując jako operator dodawania, jako operator mnożenia oraz i jako argumenty. Używając nawiasów, przy powyżej interpretacji, możemy ten język zapisać następująco:

Wprost z definicji gramatyk - regularnej i bezkontekstowej - wynika, że rodzina języków regularnych jest podrodziną rodziny języków bezkontekstowych. Z lematu o pompowaniu dla języków regularnych wiemy, że język nie jest regularny. Łatwo uzasadnić, że język ten jest bezkontekstowy, bo jest generowany przez gramatykę:

Zatem rodzina języków regularnych jest właściwą podrodziną rodziny języków bezkontekstowych, czyli

Przejdziemy teraz do omówienia pewnych własności gramatyk bezkontekstowych, które prowadzą do ich uproszczenia. Występujące w poniższym twierdzeniu sformułowanie "produkcja wymazująca" oznacza produkcję .

Twierdzenie 1.1

Niech będzie dowolną gramatyką bezkontekstową.

  1. Istnieje gramatyka bezkontekstowa bez produkcji wymazującej taka, że
  2. Jeśli , to istnieje równoważna gramatyka bezkontekstowa taka,

że jedyną produkcją wymazującą w jest produkcja i symbol nie występuje po prawej stronie żadnej produkcji z .

Dowód

Dowód podaje konstrukcję odpowiednich gramatyk. Dla dowodu punktu 1 rozważmy ciąg zbiorów

określony dla . Jest to ciąg podzbiorów taki, że . Ponieważ zbiór symboli nieterminalnych jest skończony, więc istnieje indeks taki, że . Zatem ciąg jest skończony. Stąd równoważność

Zatem wtedy i tylko wtedy, gdy Konstruujemy teraz gramatykę , przyjmując i jak w gramatyce . Natomiast nowy zbiór praw zawiera zmodyfikowane prawa gramatyki . Jeśli prawo , to do zbioru wprowadzamy prawa , gdzie i powstaje z przez wymazanie dowolnej liczby (także ) symboli ze zbioru . Pozostaje teraz uzasadnienie równości

Dowód inkluzji
Zauważmy, że dla każdego prawa istnieje prawo takie, że różni się od wyłącznie pewną ilością symboli z . Z równoważności wynika, że symbole ze zbioru prowadzą w dalszym ciągu generowania do słowa pustego. A więc dla każdego wyprowadzenia niepustego słowa w gramatyce istnieje w gramatyce wyprowadzenie tego samego słowa. Wystarczy w wyprowadzeniu w gramatyce w miejsce praw postaci wprowadzić prawa by otrzymać wyprowadzenie tego samego słowa w .

Dowód inkluzji
Określamy gramatykę pomocniczą . Zbiór praw tej gramatyki rozszerza o wszystkie prawa wymazujące ze zbioru . Z definicji wynika, że , więc . Dla dowodu wystarczy więc pokazać, że

Niech i niech będzie wyprowadzeniem słowa w . Jeśli w tym wyprowadzeniu wszystkie prawa należą do , to oczywiście słowo . Jeśli w wyprowadzeniu słowa występuje prawo wymazujące, to oznacza, że dla pewnego oraz wyprowadzenie ma postać

Jednak, jak łatwo zauważyć, słowo można także wygenerować, pomijając to prawo wymazujące i wykorzystując wyłącznie prawa z

co kończy dowód punktu 1.

Przechodząc do dowodu punktu 2, załóżmy, że i niech będzie gramatyką taką jak w punkcie 1. Definiujemy teraz gramatykę

która spełnia żądane w twierdzeniu warunki i .

End of proof.gif

Z udowodnionego powyżej twierdzenia i z definicji gramatyk bezkontekstowych i kontekstowych (definicja 2.1. z wykładu 2) wynika następujące stwierdzenie

Wniosek 1.1

Rodzina języków bezkontekstowych (typu (2)) zawiera się w rodzinie jezyków kontekstowych (typu (1))

Przejdziemy teraz do zagadnienia upraszczania gramatyki bezkontekstowej. Wprowadzimy następującą definicję.

Definicja 1.1

Mówimy, że gramatyka bezkontekstowa jest właściwa, jeśli zbiór praw nie zawiera produkcji wymazującej oraz produkcji typu , gdzie .

Lemat 1.1

Dla każdej gramatyki bezkontekstowej generującej język bez słowa pustego istnieje równoważna jej gramatyka bezkontekstowa właściwa.

Dowód

W dowodzie przedstawimy konstrukcję gramatyki o żądanych własnościach. Na podstawie udowodnionego powyżej twierdzenia możemy przyjąć, że jest bez produkcji wymazującej. Dla usunięcia produkcji w postaci określamy ciąg zbiorów dla , przyjmując oraz dla

Ciąg jest skończony (stabilizuje się), a więc dla pewnego i dla każdego mamy równość . Dla dowolnego oraz prawdziwa jest równoważność

która w szczególności dla symbolu terminalnego oznacza, że wtedy i tylko wtedy, gdy

Określamy teraz gramatykę , w której zbiór zawiera produkcje postaci:

  1. dla każdego
  2. dla , oraz dla

każdego , takiego, że istnieje prawo , i .

W gramatyce nie występują prawa postaci . Gramatyka nie zawiera praw wymazujących oraz , co kończy dowód lematu.

End of proof.gif

Dalsze rozważania prezentują mozliwości upraszczania gramatyk bezkontekstowych poprzez usunięcie pewnych nieistotnych symboli nieterminalnych, a także poprzez zastąpienie danej gramatyki przez równoważną o prostszej strukturze.

Niech będzie gramatyką bezkontekstową, generującą niepusty język. Mówimy, że symbol nieterminalny jest użyteczny, jeśli istnieje słowo i wyprowadzenie tego słowa takie, że

dla pewnych . W przeciwnym wypadku mówimy, że symbol jest bezużyteczny. Symbole nieużyteczne można usunąć z gramatyki bez uszczerbku dla generowanego przez tę gramatykę języka. Przekonuje o tym następujące twierdzenie.

Twierdzenie 1.2

Dla dowolnego niepustego języka bezkontekstowego istnieje gramatyka bezkontekstowa bez bezużytecznych symboli nieterminalnych, która generuje ten język.

Konstrukcja takiej gramatyki, a więc i dowód tego twierdzenia wynika bezpośrednio z następujących dwóch lematów.

Lemat 1.2

Dla każdej gramatyki bezkontekstowej istnieje równoważna gramatyka bezkontekstowa taka, że dla dowolnego istnieje oraz

Dowód

Określamy rekurencyjnie ciąg podzbiorów zbioru symboli nieterminalnych  :
oraz dla
. Zbiory te tworzą ciąg wstępujący i stabilizujący się dla pewnego . Oznacza to, że . Przyjmujemy z definicji oraz

Tak określona gramatyka ma własności gramatyki postulowanej w tezie lematu. Pozostaje udowodnić równoważność określonej gramatyki i gramatyki . W tym celu wystarczy pokazać dla dowolnego i , że jeśli , to . Udowodnimy tę implikację indukcyjnie ze względu na długość wyprowadzenia. Dla istnienie wyprowadzenia oznacza, że . Stąd zaś wynika, że . Dla dalszej części rozumowania załóżmy, że implikacja jest prawdziwa dla wyprowadzenia o długości nie większej od i niech

będzie wyprowadzeniem o długości dla słowa . Niech dla pewnych oraz . Oznaczmy dla słowa symbolem słowo otrzymane przez wymazanie wszystkich symboli terminalnych, a symbolem słowo otrzymane przez wymazanie wszystkich symboli nieterminalnych. Wtedy . Wówczas istnieją słowa takie, że i dla każdego istnieją wyprowadzenia o długości mniejszej lub równej od . Korzystając z założenia indukcyjnego, wnioskujemy, że dla każdego , a to oznacza z definicji , że istnieje takie, że dla każdego . Ostatecznie więc .

End of proof.gif

Lemat 1.3

Dla każdej gramatyki bezkontekstowej istnieje równoważna gramatyka bezkontekstowa taka, że dla dowolnego istnieją słowa oraz

Dowód

Dla rekurencyjnego określenia ciągu podzbiorów zbioru przyjmujemy:

oraz dla

gdzie oznacza zbiór symboli terminalnych i nieterminalnych występujących w słowie . Zbiory te tworzą stabilizujący się dla pewnego ciąg wstępujący . Przyjmijmy

Zbiór definiujemy jako zawierający te i tylko te prawa z , w których wszystkie symbole tworzące słowa należą do . Łatwo zauważyć, że tak określona gramatyka spełnia tezę lematu.

End of proof.gif

W świetle uzyskanych rezultatów dowolną gramatykę bezkontekstową generującą niepusty język można przekształcić w oparciu o Lemat 1.2 na równoważną, a następnie raz jeszcze przekształcić uzyskaną gramatykę stosując konstrukcję opisaną w dowodzie Lematu 1.3, uzyskując ostatecznie gramatykę bez bezużytecznych symboli nieterminalnych, czyli spełniającą tezę powyższego twierdzenia.

Warto podkreślić, iż istotna jest kolejność przekształcania gramatyk. Zmiana kolejności może sprawić, iż nie uzyskamy pożądanego efektu. Załóżmy, dla ilustracji, że w gramatyce istnieje wyprowadzenie dla pewnych oraz i jest to jedyna możliwość wygenerowania z słowa, w którym występuje . Istnieje także słowo i wyprowadzenie . Z symbolu nie da się natomiast w gramatyce wyprowadzić żadnego słowa terminalnego. Zastosowanie drugiego z powyższych lematów, uzasadniających twierdzenie, nie usunie symboli i z alfabetu nieterminalnego. Lemat pierwszy usunie tylko . Symbol pozostanie, pomimo iż jest bezużyteczny.

Gramatyki w postaci Chomsky'ego i Greibach

Wprowadzimy teraz określenia dwóch szczególnych postaci gramatyk bezkontekstowych, a mianowicie gramatyki w postaci normalnej Chomsky'ego oraz gramatyki w postaci normalnej Greibach.

Definicja 2.1

Gramatyka bezkontekstowa jest

  1. w postaci normalnej Chomsky'ego, jeśli wszystkie prawa są w formie:
    lub
    gdzie , .
  2. w postaci normalnej Greibach, jeśli wszystkie prawa są w formie:

gdzie .

Sheila Greibach (1939-)
Zobacz biografię

Łatwo zaobserwować, że gramatyka zarówno w postaci normalnej Chomsky'ego, jak i w postaci

Greibach jest gramatyką właściwą oraz że język generowany przez te gramatyki nie zawiera słowa pustego. Ponadto drzewo wywodu dowolnego słowa w gramatyce w postaci normalnej Chomsky'ego jest binarne.

Twierdzenie 2.1

Dla każdej gramatyki bezkontekstowej , generującej język bez słowa pustego, istnieje równoważna gramatyka w postaci normalnej Chomsky' ego.

Dowód

Zakładamy, że gramatyka jest właściwa. Konstruujemy gramatykę , gdzie jest kopią alfabetu terminalnego. Zbiór produkcji powstaje z przez zamianę w każdej produkcji, której prawa strona nie jest pojedynczą literą terminalną, symbolu na oraz dodaniu produkcji dla każdego . Prawdziwa jest równość i w gramatyce nie występują produkcje typu .

Aby uzyskać równoważną gramatykę w postaci normalnej Chomsky' ego, produkcje typu dla i występujące ewentualnie w zastępujemy

produkcjami:

dodając do zbioru symboli nieterminalnych nowe elementy . Skonstruowana w ten sposób gramatyka jest w normalnej postaci Chomsky'ego oraz .

End of proof.gif

Przedstawiamy poniżej algorytm przekształcający gramatykę bezkontekstową właściwą w gramatykę mającą postać normalną Chomsky'ego.

Algorytm PostaćNormalnaChomsky'ego - buduje gramatykę bezkontekstową w postaci normalnej Chomsky'ego



  1  Wejście:  - gramatyka bezkontekstowa właściwa.
  2  Wyjście:  - gramatyka bezkontekstowa w postaci
normalnej Chomsky'ego. 3 ; nowy zbiór produkcji budujemy sukcesywnie 4 ; tak jak i nowe symbole nieterminalne 5 ; symbole terminalne pozostają takie same 6 ; podobnie jak symbol startowy 7 for each do 8 dodaj nowy symbol nieterminalny 9 end for 10 licznik produkcji 11 for do 12 if and then 13 ; takie produkcje są dopuszczone 14 else 15 for to do 16 if then 17 ; 18 ; zmień na parę produkcji 19 end if 20 end for 21 ; nowe symbole nieterminalne 22 nowe produkcje w miejsce 23 24 for to do 25 ; 26 end for 27 end if 28 end for 29 return ;

Przykład 2.1

Gramatykę , dla której , , a zbiór praw dany jest poniżej

sprowadzimy do postaci normalnej Chomsky'ego.

Do zbioru od razu włączamy produkcje oraz . Poniżej, dla każdej z pozostałych produkcji wypisane są (po dwukropku) produkcje dodawane do :

Ostatecznie gramtyka ma postać:

Uwaga 2.1

Rozumowanie z dowodu twierdzenia o postaci Chomsky'ego można zastosować do gramatyk regularnych prawoliniowych. W wyniku tego uzyskujemy łatwo fakt, że postać normalna Chomsky'ego oznacza tu gramatykę o prawach typu:

{ lub lub . }

Podobne twierdzenie, w którym mowa o postaci normalnej Greibach podamy poniżej. Przypomnijmy następujące oznaczenie. Dla dowolnego symbolu nieterminalnego w gramatyce przez oznaczamy podzbiór zbioru produkcji zawierający wyłącznie takie produkcje, które po lewej stronie mają symbol . Twierdzenie poprzedzimy dwoma lematami. Obserwacja sformułowana w pierwszym lemacie jest oczywista

Lemat 2.1

Niech będzie gramatyką bezkontekstową, a  prawem tej gramatyki dla pewnych . Gramatyka , w której

jest równoważna .

Usuniętą produkcję nazywać będziemy niekońcową v-produkcją.

Definicja 2.2

Niech będzie gramatyką bezkontekstową.

Produkcję

gdzie , nazywamy lewostronnie rekursywną.

Kolejny lemat wskazuje możliwość wyeliminowania lewostronnej rekursji z gramatyki generującej język bezkontekstowy.

Lemat 2.2

Niech będzie gramatyką bezkontekstową oraz . Zakładając niepustość zbioru niech

. Gramatyka , gdzie ,

jest równoważna gramatyce .

Dowód

Zaobserwujmy, że w gramatyce każdy ciąg produkcji ze zbioru musi zakończyć produkcja z . Zatem wyprowadzenie

można w gramatyce przeprowadzić następująco:

W podobny sposób można każde wyprowadzenie w przeprowadzić w .

End of proof.gif

Udowodnimy teraz twierdzenie o postaci normalnej Greibach.

Twierdzenie 2.2

Dla każdej gramatyki bezkontekstowej , generującej język bez słowa pustego, istnieje równoważna gramatyka bezkontekstowa w postaci normalnej Greibach.

Dowód

Załóżmy, że gramatyka jest w postaci normalnej Chomsky'ego. W alfabecie nieterminalnym wprowadzamy porządek zadany przez indeksy symboli nieterminalnych. Gramatykę przekształcimy teraz na równoważną taką, że jeśli jest prawem nowej gramatyki, to Efekt taki uzyskamy, przekształcając prawa kolejno, zgodnie z porządkiem wprowadzonym w zbiorze i symbolem nieterminalnym występującym po lewej stronie prawa. Załóżmy, że dla pewnego , wszystkich , gdzie jest:

oraz istnieje takie, że

W oparciu o lemat 2.1 prawo zastępujemy prawami , gdzie lub , gdzie . Stąd, że , to . Powtarzamy to postępowanie (co najwyżej razy), aż uzyskamy nierówność lub prawo , gdzie . W przypadku, gdy otrzymamy , czyli lewą rekursję , stosujemy Lemat 2.2, wprowadzając nowy symbol nieterminalny . Analogicznie postępujemy, gdy w gramatyce występuje lewa rekursja dla .

W wyniku wprowadzonych przekształceń uzyskamy, równoważną wyjściowej, gramatykę ze zbiorem produkcji , w którym

gdzie pierwszą literą słowa , które występuje w trzecim typie produkcji, jest symbol nieterminalny różny od (nie jest to lewa rekursja). Zauważmy, że każda produkcja z ma postać oraz każda produkcja z ma postać lub . A więc dla każda produkcja z jest postaci lub .

Stosujemy teraz Lemat 2.1 do praw ze zbioru i , tak by prawe strony otrzymanych produkcji zaczynały się symbolem terminalnym. Następnie stosujemy Lemat 2.1 do praw ze zbioru . Po tych zmianach prawe strony produkcji zaczynają się symbolem terminalnym. Natomiast żadna z produkcji należących do dla nie jest lewą rekursją, co wynika z konstrukcji gramatyki i z Lematu 2.2. Produkcje te zaczynają się symbolem nieterminalnym i w związku z tym stosujemy kolejny raz Lemat 2.1. W rezultacie uzyskujemy bezkontekstową gramatykę w postaci normalnej Greibach równoważną wyjściowej gramatyce .

End of proof.gif

Prezentowany teraz algorytm PrzekształćDlaGreibach przekształca gramatykę bezkontekstową, realizując powyższe dwa lematy, czyli usuwając v-produkcje niekońcowe i eliminując lewostronną rekursję. Zakładamy, bez utraty ogólności, że na wejściu algorytm otrzymuje gramatykę w postaci normalnej Chomsky'ego.

Algorytm PrzekształćDlaGreibach - buduje gramatykę bezkontekstową taką, że każda produkcja jest postaci , lub jej prawa strona zaczyna się od symbolu terminalnego



  1  Wejście:  - gramatyka bezkontekstowa w postaci Chomsky'ego.
  2  Wyjście:  - gramatyka bezkontekstowa
bez niekońcowych -produkcji i bez lewostronnej rekursji. 3 ; 4 ; 5 ; 6 for to do 7 for to do 8 for to do 9 for each do 10 ; 11 for each do 12 ; 13 end for 14 end for 15 end for 16 end for 17 for to do 18 for each do 19 ; 20 end for 21 end for 22 end for 23 for to do 24 for each do 25 ; 26 ; 27 ; 28 ; 29 end for 30 for each do 31 if then 32 ; 33 end if 34 end for 35 end for 36 return ;

Kolejny algorytm PostaćNormalnaGreibach przekształca gramatykę bezkontekstową do postaci normalnej Greibach. Zakładamy, że algorytm ten otrzymuje na wejściu gramatykę bezkontekstową właściwą.

Algorytm PostaćNormalnaGreibach - buduje gramatykę bezkontekstową w postaci normalnej Greibach



  1  Wejście:  - gramatyka bezkontekstowa właściwa.
  2  Wyjście:  - gramatyka bezkontekstowa w postaci normalnej Greibach.
  3  PostaćNormalnaChomsky'ego;                            
  4  PrzekształćDlaGreibach;                   ,
  5  for   downto   do
  6    for   to   do
  7      for each  do
  8        
  9        for each  do 
 10          if  then
 11            ;
 12          end if
 13        end for
 14      end for
 15    end for
 16  end for
 17  for   to  2n+1 do
 18    for each   do
 19      
 20      for each   do
 21        
 22      end for
 23    end for
 24  end for
 25  ;
 26  return ;

Przykład 2.2

Gramatykę , dla której , , a zbiór praw dany jest poniżej

sprowadzimy do postaci normalnej Greibach.

Stosujemy procedurę PrzekształćDlaGreibach, wykorzystującą lematy 2.1 oraz 2.2. Prawe strony produkcji rozpoczynających się od i rozpoczynają się symbolami terminalnymi lub nieterminalami o wyższych indeksach niż odpowiednio 1 i 2, zatem jedyna produkcja, do której zastosujemy lemat 2.1, to . Usuwamy ją, a ponieważ prawa jej strona rozpoczyna się nieterminalem , zastępujemy ten nieterminal prawą stroną produkcji i nowo otrzymaną produkcję dodajemy do . Ponieważ pierwszy nieterminal po prawej stronie ma niższy indeks niż 3, znowu stosujemy tę samą operację: usuwamy produkcję i na jej miejsce wstawiamy produkcje powstałe w wyniku zastąpienia pierwszego z prawej jej strony łańcuchami oraz , czyli prawymi stronami produkcji, po których lewej stronie jest . Otrzymujemy zatem dwie nowe produkcje: oraz . Teraz każda produkcja jest następującej postaci: albo prawa jej strona zaczyna się terminalem, albo nieterminalem o indeksie większym lub równym indeksowi nieterminala stojącego z lewej strony.

Następny krok to wyeliminowanie lewostronnej rekursji. Stosujemy lemat 2.2 do produkcji . Usuwamy ją z i w jej miejsce wstawiamy produkcje , , .

Po zakończeniu działania procedury PrzekształćDlaGreibach otrzymujemy następującą gramatykę:

Wszystkie prawe strony produkcji mających po lewej stronie zaczynają się od terminala. W pętli (linie 5. - 16.) zastępujemy tymi prawymi stronami nieterminale stojące jako pierwsze nieterminale po prawej stronie produkcji postaci ; w naszym przypadku jedyną taką produkcją jest produkcja ; teraz zarówno produkcje postaci jak i rozpoczynają się terminalami. Po tym przekształceniu gramatyka ma postać:

Prawymi stronami produkcji postaci zastępujemy teraz nieterminale stojące jako pierwsze nieterminale po prawej stronie produkcji postaci . W naszym przypadku jedyną taką produkcją jest produkcja . Gramatyka wygląda teraz tak:

Ostatecznie, po ukończeniu pętli, każda produkcja mająca po lewej stronie , lub zaczyna się terminalem, po którym następuje ciąg nieterminali. Te produkcje są więc w postaci normalnej Greibach.

W ostatnim kroku sprowadzamy do żądanej postaci nieterminale . Obie -produkcje przekształcamy, zastępując pierwszy nieterminal stojący po ich prawych stronach (czyli ) prawymi stronami produkcji postaci . Obie -produkcje zostaną z usunięte, a na ich miejsce dodane zostaną produkcje

oraz

Ostatecznie, gramatyka w postaci Greibach ma postać: