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

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 $G=(V_N,V_T,v_0,P)$ ma postać $v\to x_1\dots .x_k$ lub $v\to 1$, gdzie $v\in V_N,x_i\in (V_N\cup V_T)$. 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 $G$ nazywane jest drzewem elementarnym. Mając dowolne wyprowadzenie w gramatyce $G$, można przedstawić je graficznie w postaci etykietowanego drzewa. Niech

$v_0\to w_1\to \dots ..\to w_n=w$

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

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

właśnie produkcja została wykorzystana w bezpośrednim wyprowadzeniu $w_i\mapsto w_{i+1}$, to znaczy we fragmencie wyprowadzenia $v_0{\mapsto }^{*}{w}_n=w$,

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

Przykład 1.1

Niech $G=(V_N,V_T,v_0,P)$, gdzie $V_N=\{v_0,v_1\},V_T=\{a,b,c\}$,
$P=\{v_0\to a{v}_{0}c,v_0\to b{v}_{1}c,v_1\to b{v}_{1}c,v_1\to bc\}$.

Wówczas wyprowadzeniu $v_0\mapsto a{v}_{0}c\mapsto ab{v}_{1}cc\mapsto abbccc$ odpowiada drzewo

Rysunek 2

W poniższym przykładzie, jak i w dalszych wykładach symbolem $\bar{A}$ oznaczamy kopię alfabetu $A$, 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ę $G=(V_N,V_T,v_0,P)$, w której $V_N=\{v_0,v_1\},V_T=A\cup \bar{A},;A=\left\{a\right\},;\bar{A}=\left\{\bar{a}\right\},P=$
   $\{v_0\to 1,v_0\to v_1{v}_0,v_1\to a{v}_0\bar{a}\}$.
   Język generowany przez tę gramatykę, nazywany językiem Dycka, oznaczany jest przez $D_A^{*}$. Język Dycka zwany jest też językiem "poprawnych nawiasów" przy interpretacji symboli $a,\bar{a}$ jako lewego i prawego nawiasu. $L(G)=\{1,a\bar{a},aa\bar{a}\bar{a},a\bar{a}a\bar{a},aa\bar{a}\bar{a}a\bar{a},\dots \}$ Język Dycka można zdefiniować także dla alfabetu $A=\{a_1,\dots ,a_n\}$ mającego więcej niż dwa symbole. Do zbioru praw gramatyki $G$ wprowadza się wszystkie możliwe prawa postaci $v_1\to a_i{v}_0\overline{a_i}$. W tym przypadku dla języka Dycka używa się oznaczenia $D_n^{*}$, aby zaznaczyć liczbę elementów alfabetu $A$.
2. Język Łukasiewicza.
   Język Łukasiewicza jest generowany przez gramatykę bezkontekstową $G=(V_N,V_T,v_0,P)$, gdzie $V_N=\{v_0\}$, $V_T=\{a,b,+,*\}$,$v_0=v$ oraz $P=\{v\to a,v\to b,v\to +vv,v\to *vv\}$. Język Łukasiewicza jest więc zbiorem $L(G)=\{a,:b,+ab,*b+ab,*+ab+ab,\dots \}$
   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 $a$ i $b$ jako argumenty. Używając nawiasów, przy powyżej interpretacji, możemy ten język zapisać następująco:

$L(G)=\{a,:b,:a+b,:b*(a+b),:(a+b)*(a+b),\dots \}$

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 $L=\{a^n{b}^n:n=1,2,\dots \}$ nie jest regularny. Łatwo uzasadnić, że język ten jest bezkontekstowy, bo jest generowany przez gramatykę:

$G=(\{v_0,v_1\},\{a,b\},v_0,\{v_0\to a{v}_{1}b,v_1\to 1,v_1\to a{v}_{1}b\})$.

Zatem rodzina języków regularnych jest właściwą podrodziną rodziny języków bezkontekstowych, czyli ${{ℒ}}_3\subseteq {}_{/}{{ℒ}}_2$

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ę $v\to 1$ .

Twierdzenie 1.1

Niech $G=(V_N,V_T,v_0,P)$ będzie dowolną gramatyką bezkontekstową.

1. Istnieje gramatyka bezkontekstowa $G^{\prime }$ bez produkcji wymazującej taka, że $L(G^{\prime })=L(G)\mathrm{\setminus }\{1\}$.
2. Jeśli $1\in L(G)$, to istnieje równoważna $G$ gramatyka bezkontekstowa $G^{″}=(V^{\prime }{\text{'}}_N,V_T,{v_0}^{″},P^{″})$ taka,

że jedyną produkcją wymazującą w $P^{″}$ jest produkcja ${v_0}^{″}\to 1$ i symbol ${v_0}^{″}$ nie występuje po prawej stronie żadnej produkcji z $P^{″}$.

Dowód

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

$\begin{array}{l}{U}_1=\{v\in V_N:v\to 1\in P\},\\ U_{i+1}=U_i\cup \{v\in V_N:v\to x\in P,x\in U_i^{*}\}\end{array}$

określony dla $i=1,2\dots$ . Jest to ciąg podzbiorów $V_N$ taki, że $U_1\subseteq U_2\subseteq \dots \subseteq V_N$. Ponieważ zbiór symboli nieterminalnych $V_N$ jest skończony, więc istnieje indeks $k$ taki, że $U_k=U_{k+1}$. Zatem ciąg $U_i$ jest skończony. Stąd równoważność

$v\underset{G}{\overset{*}{\mapsto }}1⟺v\in U_k.(*)$

Zatem $1\in L(G)$ wtedy i tylko wtedy, gdy $v_0\in U_k$. Konstruujemy teraz gramatykę $G^{\prime }=(V_N,V_T,v_0,P^{\prime })$, przyjmując $V_N,V_T$ i $v_0$ jak w gramatyce $G$ . Natomiast nowy zbiór praw $P^{\prime }$ zawiera zmodyfikowane prawa gramatyki $G$ . Jeśli prawo $v\to x\in P$ , to do zbioru $P^{\prime }$ wprowadzamy prawa $v\to x^{\prime }$ , gdzie $x^{\prime }\ne 1$ i $x^{\prime }$ powstaje z $x$ przez wymazanie dowolnej liczby (także $0$ ) symboli ze zbioru $U_k$ . Pozostaje teraz uzasadnienie równości

$L(G^{\prime })=L(G)-\left\{1\right\}$

Dowód inkluzji $\subseteq$
Zauważmy, że dla każdego prawa $v\to x^{\prime }\in P^{\prime }$ istnieje prawo $v\to x\in P$ takie, że $x$ różni się od $x^{\prime }$ wyłącznie pewną ilością symboli z $U_k$ . Z równoważności $(*)$ wynika, że symbole ze zbioru $U_k$ prowadzą w dalszym ciągu generowania do słowa pustego. A więc dla każdego wyprowadzenia niepustego słowa w gramatyce $G^{\prime }$ istnieje w gramatyce $G$ wyprowadzenie tego samego słowa. Wystarczy w wyprowadzeniu w gramatyce $G^{\prime }$ w miejsce praw postaci $v\to x^{\prime }\in P^{\prime }$ wprowadzić prawa $v\to x\in P$ by otrzymać wyprowadzenie tego samego słowa w $G$ .

Dowód inkluzji $\supseteq$
Określamy gramatykę pomocniczą $\bar{G}=(V_N,V_T,v_o,P\cup P^{\prime })$ . Zbiór praw tej gramatyki rozszerza $P^{\prime }$ o wszystkie prawa wymazujące ze zbioru $P$ . Z definicji wynika, że $L(G)\subseteq L(\bar{G})$ , więc $L(G)-\left\{1\right\}\subseteq L(\bar{G})-\left\{1\right\}$ . Dla dowodu wystarczy więc pokazać, że

$L(\bar{G})-\left\{1\right\}\subseteq L(G^{\prime })$.

Niech $w\in L(\bar{G})-\left\{1\right\}$ i niech $v_0{\mapsto }_{\bar{G}}....{\mapsto }_{\bar{G}}w$ będzie wyprowadzeniem słowa $w$ w $\bar{G}$ . Jeśli w tym wyprowadzeniu wszystkie prawa należą do $P^{\prime }$ , to oczywiście słowo $w\in L(G^{\prime })$ . Jeśli w wyprowadzeniu słowa $w$ występuje prawo wymazujące, to oznacza, że dla pewnego $y_i\in U_k,x_p\to v_1{v}_2\in P^{\prime }$ oraz $x_p\to v_1{y}_i{v}_2\in P^{\prime }$ wyprowadzenie ma postać

$\begin{array}{ccccc}& x_p\to v_1{y}_i{v}_2& & y_i\to 1& \\ v_0\mapsto \cdots x_1\dots x_p\dots x_n& \mapsto & x_1\dots v_1{y}_i{v}_2\dots y_m& \mapsto & \end{array}$ $\mapsto x_1\dots v_1{v}_2\dots x_n\mapsto \cdots \mapsto w$

Jednak, jak łatwo zauważyć, słowo $w$ można także wygenerować, pomijając to prawo wymazujące i wykorzystując wyłącznie prawa z $P^{\prime }$

$\begin{array}{cccc}& x_p\to v_1{v}_2& & \\ v_0\mapsto x_1\dots x_p\dots x_n& \mapsto & x_1\dots v_1{v}_2\dots x_n& \mapsto \cdots \mapsto w,\end{array}$

co kończy dowód punktu 1.

Przechodząc do dowodu punktu 2, załóżmy, że $1\in L(G)$ i niech $G^{\prime }$ będzie gramatyką taką jak w punkcie 1. Definiujemy teraz gramatykę

$G^{″}=(V_N\cup \left\{v_{0^{″}}\right\},V_T,v_{0^{″}},P^{\prime }\cup \{v_{0^{″}}\to 1,:v_{0^{″}}\to v_0\})$,

która spełnia żądane w twierdzeniu warunki i $L(G)=L(G^{″})$ .

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))

${{ℒ}}_2\subseteq {{ℒ}}_1$.

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

Definicja 1.1

Mówimy, że gramatyka bezkontekstowa $G$ jest właściwa, jeśli zbiór praw nie zawiera produkcji wymazującej oraz produkcji typu $v_1\to v_2$, gdzie $v_1,v_2\in V_N$ .

Lemat 1.1

Dla każdej gramatyki bezkontekstowej $G$ generującej język bez słowa pustego istnieje równoważna jej gramatyka bezkontekstowa $H$ 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 $G=(V_N,V_T,v_0,P)$ jest bez produkcji wymazującej. Dla usunięcia produkcji w postaci $v_1\to v_2$ określamy ciąg zbiorów $U_i(x)$ dla $x\in V_N\cup V_T$, przyjmując $U_1(x)=\left\{x\right\}$ oraz dla $i=1,2\dots U_{i+1}(x)=U_i(x)\cup \{y\in V_N\cup V_T:\mathrm{\exists }u\in U_i(x),u\to y\in P\}$

Ciąg $U_i(x)$ jest skończony (stabilizuje się), a więc $U_k(x)=U_{k+1}(x)$ dla pewnego $k$ i dla każdego $l>k$ mamy równość $U_l(x)=U_k(x)$. Dla dowolnego $v\in V_N$ oraz $z\in V_N\cup V_T$ prawdziwa jest równoważność

$v{\mapsto }^{*}z⟺z\in U_k(v)$,

która w szczególności dla symbolu terminalnego $a\in V_T$ oznacza, że $a\in L(G)$ wtedy i tylko wtedy, gdy $a\in U_k(v_0)$.

Określamy teraz gramatykę $H=(V_N,V_T,v_0,\bar{P})$ , w której zbiór $\bar{P}$ zawiera produkcje postaci:

1. $v_0\to a$ dla każdego $a\in V_T\cap U_k(v_0)$,
2. $v\to z_1...z_n$ dla $v\in V_N$, $n⩾2$ oraz dla

każdego $z_j\in V_N\cup V_T$, $j=1,\dots ,n$ takiego, że istnieje prawo $\bar{v}\to x_1...x_n\in P$, $\bar{v}\in U_k(v)$ i $z_j\in U_k(x_j)$.

W gramatyce $H$ nie występują prawa postaci $v_1⟶v_2$. Gramatyka $H$ nie zawiera praw wymazujących oraz $L(G)=L(H)$, co kończy dowód lematu.

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 $G=(V_N,V_T,v_0,P)$ będzie gramatyką bezkontekstową, generującą niepusty język. Mówimy, że symbol nieterminalny $v\in V_N$ jest użyteczny, jeśli istnieje słowo $w\in L(G)$ i wyprowadzenie tego słowa takie, że

$v_0{\mapsto }^{*}xvy{\mapsto }^{*}w$

dla pewnych $x,y\in (V_N\cup V_T{)}^{*}$ . W przeciwnym wypadku mówimy, że symbol $v$ 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 $L$ 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 $G=(V_N,V_T,v_0,P)$ istnieje równoważna gramatyka bezkontekstowa $\bar{G}=({\bar{V}}_N,V_T,v_0,\bar{P})$ taka, że dla dowolnego $v\in {\bar{V}}_N$ istnieje $w\in V_T^{*}$ oraz

$v\underset{\bar{G}}{\overset{*}{\mapsto }}w$

Dowód

Określamy rekurencyjnie ciąg podzbiorów zbioru symboli nieterminalnych $V_N$ :
$U_1=\{v\in V_N:::v\to w\in P,:w\in V_T^{*}\}$ oraz dla $i=1,2,\dots$
$U_{i+1}=U_i\cup \{v\in V_N::::v\to x\in P,:x\in (U_i\cup V_T{)}^{*}\}$ . Zbiory te tworzą ciąg wstępujący i stabilizujący się dla pewnego $p$ . Oznacza to, że $U_1\subseteq U_2\subseteq \dots \subseteq U_p=U_{p+1}$ . Przyjmujemy z definicji ${\bar{V}}_N=U_p$ oraz

$\bar{P}=\{v\to x\in P,:v\in {\bar{V}}_N,:x\in (V_T\cup {\bar{V}}_N{)}^{*}\}$

Tak określona gramatyka $\bar{G}=({\bar{V}}_N,V_T,v_0,\bar{P})$ ma własności gramatyki postulowanej w tezie lematu. Pozostaje udowodnić równoważność określonej gramatyki $\bar{G}$ i gramatyki $G$ . W tym celu wystarczy pokazać dla dowolnego $v\in V_N$ i $w\in V_T^{*}$ , że jeśli $v\underset{G}{\overset{*}{\mapsto }}w$ , to $v\in {\bar{V}}_N$ . Udowodnimy tę implikację indukcyjnie ze względu na długość wyprowadzenia. Dla $n=1$ istnienie wyprowadzenia $v\underset{G}{\overset{*}{\mapsto }}w$ oznacza, że $v\to w\in P$ . Stąd zaś wynika, że $v\in U_1\subset {\bar{V}}_N$ . Dla dalszej części rozumowania załóżmy, że implikacja jest prawdziwa dla wyprowadzenia o długości nie większej od $n$ i niech

$v{\mapsto }_{G}z\underset{G}{\overset{*}{\mapsto }}w$

będzie wyprowadzeniem o długości $n+1$ dla słowa $w\in V_T^{*}$ . Niech $z=y_1{v}_1{y}_2{v}_2\dots v_k{y}_{k+1}$ dla pewnych $v_1,\dots ,v_k\in V_N$ oraz $y_1,\dots ,y_{k+1}\in V_T^{*}$ . Oznaczmy dla słowa $z$ symbolem $N(z)$ słowo otrzymane przez wymazanie wszystkich symboli terminalnych, a symbolem $T(z)$ słowo otrzymane przez wymazanie wszystkich symboli nieterminalnych. Wtedy $N(z)=v_1\dots v_k,T(z)=y_1\dots y_{k+1}$ . Wówczas istnieją słowa $w_1,\dots ,w_k\in V_T^{*}$ takie, że $w=y_1{w}_1{y}_2\dots y_k{w}_k{y}_{k+1}$ i dla każdego $i=1,\dots ,k$ istnieją wyprowadzenia $v_i\underset{G}{\overset{*}{\mapsto }}{w}_i$ o długości mniejszej lub równej od $n$ . Korzystając z założenia indukcyjnego, wnioskujemy, że dla każdego $i=1,\dots ,k,::v_i\in {\bar{V}}_N$ , a to oznacza z definicji ${\bar{V}}_N$ , że istnieje $j$ takie, że dla każdego $i=1,\dots ,k,::v_i\in U_j$ . Ostatecznie więc $v\in {\bar{V}}_N$ .

Lemat 1.3

Dla każdej gramatyki bezkontekstowej $G=(V_N,V_T,v_0,P)$ istnieje równoważna gramatyka bezkontekstowa $\overline{\stackrel{‾}{G}}=({\overline{\stackrel{‾}{V}}}_N,{\overline{\stackrel{‾}{V}}}_T,v_0,\overline{\stackrel{‾}{P}})$ taka, że dla dowolnego $x\in {\overline{\stackrel{‾}{V}}}_N\cup {\overline{\stackrel{‾}{V}}}_T$ istnieją słowa $u_1,u_2\in ({\overline{\stackrel{‾}{V}}}_N\cup {\overline{\stackrel{‾}{V}}}_T{)}^{*}$ oraz

$v_0\underset{\overline{\stackrel{‾}{G}}}{\overset{*}{\mapsto }}{u}_{1}x{u}_2$.

Dowód

Dla rekurencyjnego określenia ciągu podzbiorów zbioru $V_N\cup V_T$ przyjmujemy:

$U_1=\left\{v_0\right\}$ oraz dla $k=1,2,\dots U_{k+1}=U_k\cup \{x\in alp{h}_{(V_N\cup V_T)}y:::v\to y\in P,:v\in U_k\}$

gdzie $alp{h}_{(V_N\cup V_T)}y$ oznacza zbiór symboli terminalnych i nieterminalnych występujących w słowie $y$ . Zbiory te tworzą stabilizujący się dla pewnego $p$ ciąg wstępujący $U_1\subseteq U_2\subseteq \dots \subseteq U_p=U_{p+1}$ . Przyjmijmy

${\overline{\stackrel{‾}{V}}}_N=U_P\cap V_N,:::{\overline{\stackrel{‾}{V}}}_T=U_P\cap V_T$.

Zbiór $\overline{\stackrel{‾}{P}}$ definiujemy jako zawierający te i tylko te prawa z $P$ , w których wszystkie symbole tworzące słowa należą do ${\overline{\stackrel{‾}{V}}}_N\cup {\overline{\stackrel{‾}{V}}}_T$ . Łatwo zauważyć, że tak określona gramatyka $\overline{\stackrel{‾}{G}}=({\overline{\stackrel{‾}{V}}}_N,{\overline{\stackrel{‾}{V}}}_T,v_0,\overline{\stackrel{‾}{P}})$ spełnia tezę lematu.

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 $G=(V_N,V_T,v_0,P)$ istnieje wyprowadzenie $v_0\underset{G}{\overset{*}{\mapsto }}{u}_1{v}_1{u}_2{v}_2{u}_3$ dla pewnych $v_1,v_2\in V_N$ oraz $u_1,u_2,u_3\in (V_N\cup V_T{)}^{*}$ i jest to jedyna możliwość wygenerowania z $v_0$ słowa, w którym występuje $v_1$ . Istnieje także słowo $w\in V_T^{*}$ i wyprowadzenie $v_1\underset{G}{\overset{*}{\mapsto }}w$ . Z symbolu $v_2$ nie da się natomiast w gramatyce $G$ wyprowadzić żadnego słowa terminalnego. Zastosowanie drugiego z powyższych lematów, uzasadniających twierdzenie, nie usunie symboli $v_1$ i $v_2$ z alfabetu nieterminalnego. Lemat pierwszy usunie tylko $v_2$ . Symbol $v_1$ 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 $G=(V_N,V_T,v_0,P)$ jest

1. w postaci normalnej Chomsky'ego, jeśli wszystkie prawa są w formie: $v\to v_1{v}_2$ lub $v\to a$, gdzie $v,v_1,v_2\in V_N$, $a\in V_T$.
2. w postaci normalnej Greibach, jeśli wszystkie prawa są w formie:

$v\to ax$,

gdzie $a\in V_T,:x\in V_N^{*}$ .

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 $G$, generującej język bez słowa pustego, istnieje równoważna gramatyka $H$ w postaci normalnej Chomsky' ego.

Dowód

Zakładamy, że gramatyka $G=(V_N,V_T,v_0,P)$ jest właściwa. Konstruujemy gramatykę $H_1=(V_N\cup {\bar{V}}_T,V_T,v_0,P_1)$ , gdzie ${\bar{V}}_T=\{v_a:a\in V_T\}$ jest kopią alfabetu terminalnego. Zbiór produkcji $P_1$ powstaje z $P$ przez zamianę w każdej produkcji, której prawa strona nie jest pojedynczą literą terminalną, symbolu $a$ na $v_a$ oraz dodaniu produkcji $v_a\to a$ dla każdego $a\in V_T$ . Prawdziwa jest równość $L(G)=L(H_1)$ i w gramatyce $H_1$ nie występują produkcje typu $v\to \bar{v}$.

Aby uzyskać równoważną gramatykę $H$ w postaci normalnej Chomsky' ego, produkcje typu $v\to v_1...v_n$ dla $n⩾2$ i $v_i\in V_N$ występujące ewentualnie w $H_1$ zastępujemy

produkcjami: $v\to v_1{u}_1,u_1\to v_2{u}_2,...,u_{n-2}\to v_{n-1}{v}_n$,

dodając do zbioru symboli nieterminalnych nowe elementy $u_1,\dots ,u_{n-2}$ . Skonstruowana w ten sposób gramatyka $H$ jest w normalnej postaci Chomsky'ego oraz $L(G)=L(H)$ .

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: $G=(V_N,V_T,v_0,P)$ - gramatyka bezkontekstowa właściwa.
  2  Wyjście: $G^{\prime }=({V_N}^{\prime },{V_T}^{\prime },{v_0}^{\prime },P^{\prime })$ - gramatyka bezkontekstowa w postaci
     normalnej Chomsky'ego.
  3  $P^{\prime }\leftarrow \mathrm{\varnothing }$;                           $▹$ nowy zbiór produkcji budujemy sukcesywnie 
  4  ${V_N}^{\prime }\leftarrow V_N$;                            $▹$ tak jak i nowe symbole nieterminalne
  5  ${V_T}^{\prime }\leftarrow V_T$;                          $▹$ symbole terminalne pozostają takie same
  6  ${v_0}^{\prime }\leftarrow v_0$;                                      $▹$ podobnie jak symbol startowy
  7  for each  $a\in {V_T}^{\prime }$ do
  8    ${V_N}^{\prime }\leftarrow {V_N}^{\prime }\cup \{v_a\}$                          $▹$ dodaj nowy symbol nieterminalny
  9  end for
 10  $k\leftarrow 1$                                                    $▹$ licznik produkcji
 11  for $(v\to x_1{x}_2...x_m)\in P$ do
 12    if $m=1$  and  $x_1\in V_T$ then
 13      $P^{\prime }\leftarrow P^{\prime }\cup \{v\to x_1\}$;                     $▹$ takie produkcje są dopuszczone
 14    else
 15      for $i\leftarrow 1$  to  $m$ do
 16        if $x_i\in {V_T}^{\prime }$ then
 17          $P^{\prime }\leftarrow P^{\prime }\cup \{v_{x_i}\to x_i\}$;
 18          $x_i\leftarrow v_{x_i}$;                    $▹$ zmień $(v\to x_1{x}_2...x_m)$ na parę produkcji
 19        end if
 20      end for
 21      ${V_N}^{\prime }\leftarrow {V_N}^{\prime }\cup \{u_1^k,u_2^k,\dots ,u_{m-2}^k\}$;                $▹$ nowe symbole nieterminalne
 22      $P^{\prime }\leftarrow P^{\prime }\cup \{v\to x_1{u}_1^k\}$           $▹$ nowe produkcje w miejsce $(v\to x_1{x}_2...x_m)$
 23      $P^{\prime }\leftarrow P^{\prime }\cup \{u_{m-2}\to x_{m-1}{x}_m\}$
 24      for $i\leftarrow 1$  to  $m-3$ do
 25        $P^{\prime }\leftarrow P^{\prime }\cup \{u_i\to x_{i+1}{u}_{i+1}\}$;
 26      end for
 27    end if
 28  end for
 29  return $G^{\prime }=({V_N}^{\prime },{V_T}^{\prime },{v_0}^{\prime },P^{\prime })$;

Przykład 2.1

Gramatykę $G=(V_N,V_T,v_0,P)$ , dla której $V_N=\{v_0,u,w\}$, $V_T=\{a,b\}$, a zbiór praw dany jest poniżej

$\begin{array}{rl}{v}_0& \to bu|aw\\ u& \to buu|a{v}_{0}b|a\\ w& \to aaww|b\end{array}$

sprowadzimy do postaci normalnej Chomsky'ego.

Do zbioru $P^{\prime }$ od razu włączamy produkcje $u\to a$ oraz $w\to b$. Poniżej, dla każdej z pozostałych produkcji wypisane są (po dwukropku) produkcje dodawane do $P^{\prime }$:

$\begin{array}{rl}{v}_0\to bu& :v_b\to b;v_0\to v_{b}u\\ v_0\to aw& :v_a\to a;v_0\to v_{a}w\\ u\to buu& :u\to v_b{d}_1;d_1\to uu\\ u\to a{v}_{0}b& :u\to v_a{d}_2;d_2\to v_0{v}_b\\ w\to aaww& :w\to v_a{d}_3;d_3\to v_a{d}_4;d_4\to ww\end{array}$

Ostatecznie gramtyka ma postać:

$\begin{array}{rl}{v}_0& \to v_{b}u|v_{a}w\\ u& \to v_b{d}_1|v_a{d}_2|a\\ w& \to v_a{d}_3|b\\ d_1& \to uu\\ d_2& \to v_0{v}_b\\ d_3& \to v_a{d}_4\\ d_4& \to ww\\ v_a& \to a\\ v_b& \to b\end{array}$

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:

{ $v\to a{v}^{\prime }$ lub $v\to a$ lub $v\to 1$. }

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

Lemat 2.1

Niech $G=(V_N,V_T,v_0,P)$ będzie gramatyką bezkontekstową, a  $v\to xuy$ prawem tej gramatyki dla pewnych $v,u\in V_N,x,y\in {(V_N\cup V_T)}^{*}$ . Gramatyka $\bar{G}=(V_N,V_T,v_0,\bar{P})$ , w której

$\bar{P}=(P-\{v\to xuy\})\cup \{v\to xzy:u\to z\in P\}$

jest równoważna $G$ .

Usuniętą produkcję $v\to xuy$ nazywać będziemy niekońcową v-produkcją.

Definicja 2.2

Niech $G=(V_N,V_T,v_0,P)$ będzie gramatyką bezkontekstową.

Produkcję $v\to vx$,

gdzie $v\in V_N$, $x\in (V_N\cup V_T{)}^{*}$ nazywamy lewostronnie rekursywną.

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

Lemat 2.2

Niech $G=(V_N,V_T,v_0,P)$ będzie gramatyką bezkontekstową oraz $v\in V_N$ . Zakładając niepustość zbioru $P_1(v)=\{v\to vx\in P(v):x\in {(V_N\cup V_T)}^{*}\}$ niech

$P_2(v)=P(v)-P_1(v)$ . Gramatyka $\bar{G}=(V_N\cup \left\{u\right\},V_T,v_0,\bar{P})$ , gdzie $u\notin V_N$ ,

$\bar{P}=(P-P_1(v))\cup \{v\to xu:v\to x\in P_2(v)\}\cup \{u\to x:v\to vx\in P_1(v)\}\cup \{u\to xu:v\to vx\in P_1(v)\}$

jest równoważna gramatyce $G$ .

Dowód

Zaobserwujmy, że w gramatyce $G$ każdy ciąg produkcji ze zbioru $P_1(v)$ musi zakończyć produkcja z $P_2(v)$ . Zatem wyprowadzenie

$v{\mapsto }_{G}v{x}_1{\mapsto }_{G}v{x}_2{x}_1{\mapsto }_G\cdots \cdots {\mapsto }_{G}v{x}_k\dots x_1{\mapsto }_{G}x{x}_k\dots x_1$

można w gramatyce $\bar{G}$ przeprowadzić następująco:

$v{\mapsto }_{\bar{G}}xu{\mapsto }_{\bar{G}}x{x}_{k}u{\mapsto }_{\bar{G}}\cdots {\mapsto }_{\bar{G}}x{x}_k\cdots x_{2}u{\mapsto }_{\bar{G}}x{x}_k\dots x_1$

W podobny sposób można każde wyprowadzenie w $\bar{G}$ przeprowadzić w $G$ .

Udowodnimy teraz twierdzenie o postaci normalnej Greibach.

Twierdzenie 2.2

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

Dowód

Załóżmy, że gramatyka $G$ jest w postaci normalnej Chomsky'ego. W alfabecie nieterminalnym $V_N=\{v_0,\dots ,v_n\}$ wprowadzamy porządek zadany przez indeksy symboli nieterminalnych. Gramatykę $G$ przekształcimy teraz na równoważną taką, że jeśli $v_i\to v_{j}x$ jest prawem nowej gramatyki, to $j>i$ Efekt taki uzyskamy, przekształcając prawa kolejno, zgodnie z porządkiem wprowadzonym w zbiorze $V_N$ i symbolem nieterminalnym występującym po lewej stronie prawa. Załóżmy, że dla pewnego $k$, wszystkich $i=0,\dots ,k-1$ , gdzie $1⩽k⩽n$ jest:

$\text{jeśli }{v}_i\to v_{j}x\text{jest prawem},\text{to}j>i$

oraz istnieje $j<k$ takie, że

$v_k\to v_{j}x\text{jest prawem}$.

W oparciu o lemat 2.1 prawo $v_k\to v_{j}x$ zastępujemy prawami $v_k\to v_{l}yx$ , gdzie $v_j\to v_{l}y\in P$ lub $v_k\to ayx$ , gdzie $v_j\to ay\in P$ . Stąd, że $j<k$ , to $l>j$ . Powtarzamy to postępowanie (co najwyżej $k-1$ razy), aż uzyskamy nierówność $l⩾k$ lub prawo $v_k\to ax$ , gdzie $a\in V_T$ . W przypadku, gdy otrzymamy $l=k$ , czyli lewą rekursję $v_k\to v_{k}x$ , stosujemy Lemat 2.2, wprowadzając nowy symbol nieterminalny $v_{n+k+1}$ . Analogicznie postępujemy, gdy w gramatyce $G$ występuje lewa rekursja $v_k\to v_{k}x$ dla $k=0,\dots ,n$.

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

$\begin{array}{ll}{v}_i\to v_{j}x\text{oraz}& j>i,i=0,\dots ,n-1,j=1,\dots ,n\\ v_i\to ax,\text{gdzie}& i=0,\dots ,n,a\in V_T\\ v_i\to x,\text{gdzie}& i=n+1,\dots ,2n+1,\end{array}$

gdzie pierwszą literą słowa $x$, które występuje w trzecim typie produkcji, jest symbol nieterminalny różny od $v_i$ (nie jest to lewa rekursja). Zauważmy, że każda produkcja z $\bar{P}(v_n)$ ma postać $v_n\to ax$ oraz każda produkcja z $\bar{P}(v_{n-1})$ ma postać $v_{n-1}\to v_{n}x$ lub $v_{n-1}\to ax$ . A więc dla $i=0,\dots ,n$ każda produkcja z $\bar{P}(v_i)$ jest postaci $v_i\to v_{j}x,:j>i$ lub $v_i\to ax$ .

Stosujemy teraz Lemat 2.1 do praw ze zbioru $\bar{P}(v_n)$ i $\bar{P}(v_{n-1})$ , tak by prawe strony otrzymanych produkcji zaczynały się symbolem terminalnym. Następnie stosujemy Lemat 2.1 do praw ze zbioru $\bar{P}(v_{n-2}),\dots ,\bar{P}(v_1)$ . Po tych zmianach prawe strony produkcji zaczynają się symbolem terminalnym. Natomiast żadna z produkcji należących do $\bar{P}(v_i)$ dla $i=n+1,\dots ,2n+1$ nie jest lewą rekursją, co wynika z konstrukcji gramatyki $\bar{G}$ 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ę $H$ w postaci normalnej Greibach równoważną wyjściowej gramatyce $G$ .

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 $v_k\to v_{j}x$, $k<j$ lub jej prawa strona zaczyna się od symbolu terminalnego

---

  1  Wejście: $G=(V_N,V_T,v_0,P)$ - gramatyka bezkontekstowa w postaci Chomsky'ego.
  2  Wyjście: $G^{\prime }=({V_N}^{\prime },V_T,v_0,P^{\prime })$ - gramatyka bezkontekstowa
 bez niekońcowych $v$-produkcji i bez lewostronnej rekursji.
  3  ${V_N}^{\prime }\leftarrow V_N$;                                                  $▹{V_N}^{\prime }=\{v_0,\dots ,v_n\}$
  4  ${V_T}^{\prime }\leftarrow V_T$;
  5  $P^{\prime }\leftarrow P$;
  6  for $k\leftarrow 1$  to  $n$ do
  7    for $r=1$  to  $k$ do
  8      for $j=0$  to  $k-1$ do
  9        for each $(v_k\to v_j{x}_1\dots x_s)\in P^{\prime }$ do
 10          $P^{\prime }\leftarrow P^{\prime }\mathrm{\setminus }\{v_k\to v_j{x}_1\dots x_s\}$;
 11          for each $(v_j\to y_1\dots y_l)\in P^{\prime }$ do
 12            $P^{\prime }\leftarrow P^{\prime }\cup \{v_k\to y_1\dots y_l{x}_1\dots x_s\}$;
 13          end for
 14        end for
 15      end for
 16    end for
 17    for $j=0$  to  $k-1$ do
 18      for each $(v_k\to v_j{x}_1\dots x_s)\in P^{\prime }$ do
 19        $P^{\prime }\leftarrow P^{\prime }\mathrm{\setminus }\{v_k\to v_j{x}_1\dots x_s\}$;
 20      end for
 21    end for
 22  end for
 23  for $k\leftarrow 0$ to  $n$ do
 24    for each $(v_k\to v_k{x}_1\dots x_s)\in P^{\prime }$ do
 25      ${V_N}^{\prime }\leftarrow {V_N}^{\prime }\cup \{v_{n+k+1}\}$;
 26      $P^{\prime }\leftarrow P^{\prime }\mathrm{\setminus }\{v_k\to v_k{x}_1\dots x_s\}$;
 27      $P^{\prime }\leftarrow P^{\prime }\cup \{v_{n+k+1}\to x_1\dots x_s\}$;
 28      $P^{\prime }\leftarrow P^{\prime }\cup \{v_{n+k+1}\to x_1\dots x_s{v}_{n+k+1}\}$;
 29    end for
 30    for each $(v_k\to y_1\dots y_s)\in P^{\prime }$ do 
 31      if $y_1\ne v_k$ then
 32        $P^{\prime }\leftarrow P^{\prime }\cup \{v_k\to y_1\dots y_s{v}_{n+k+1}\}$;
 33      end if
 34    end for
 35  end for
 36  return $G^{\prime }=({V_N}^{\prime },V_T,v_0,P^{\prime })$;

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: $G=(V_N,V_T,v_0,P)$ - gramatyka bezkontekstowa właściwa.
  2  Wyjście: $G^{\prime }=({V_N}^{\prime },{V_T}^{\prime },{v_0}^{\prime },P^{\prime })$ - gramatyka bezkontekstowa w postaci normalnej Greibach.
  3  $G\leftarrow$PostaćNormalnaChomsky'ego$(G)$;                            $▹V_N=\{v_0,\dots ,v_n\}$
  4  $G^{\prime }\leftarrow$PrzekształćDlaGreibach$(G)$;                   $▹{V_N}^{\prime }\subset \{v_0,\dots ,v_{2n+1}\}$,${V_T}^{\prime }=V_T$
  5  for $i\leftarrow n-1$  downto  $0$ do
  6    for $j\leftarrow 1$  to  $n-i$ do
  7      for each $(v_i\to v_{i+j}{x}_1\dots x_s)\in P^{\prime }$ do
  8        $P^{\prime }\leftarrow P^{\prime }\setminus \{v_i\to v_{i+j}{x}_1\dots x_s\}$
  9        for each $(v_{i+j}\to z_1\dots z_l)\in P^{\prime }$ do 
 10          if $z_1\in V_T$ then
 11            $P^{\prime }\leftarrow P^{\prime }\cup \{v_i\to z_1\dots z_l{x}_1\dots x_s\}$;
 12          end if
 13        end for
 14      end for
 15    end for
 16  end for
 17  for $i\leftarrow n+1$  to  2n+1 do
 18    for each  $(v_i\to x_1\dots x_s)\in P^{\prime }$ do
 19      $P^{\prime }\leftarrow P^{\prime }\setminus \{v_i\to x_1\dots x_s\}$
 20      for each  $(x_1\to z_1\dots z_l)\in P^{\prime }$ do
 21        $P^{\prime }\leftarrow P^{\prime }\cup \{v_i\to z_1\dots z_l{x}_2\dots x_s\}$
 22      end for
 23    end for
 24  end for
 25  ${v_0}^{\prime }\leftarrow v_0$;
 26  return $G^{\prime }=({V_N}^{\prime },{V_T}^{\prime },{v_0}^{\prime },P^{\prime })$;

Przykład 2.2

Gramatykę $G=(V_N,V_T,v_1,P)$ , dla której $V_N=\{v_1,v_2,v_3\}$, $V_T=\{a,b\}$, a zbiór praw dany jest poniżej

$\begin{array}{rl}{v}_1& \to v_2{v}_3\\ v_2& \to v_3{v}_1|b\\ v_3& \to v_1{v}_2|a,\end{array}$

sprowadzimy do postaci normalnej Greibach.

Stosujemy procedurę PrzekształćDlaGreibach, wykorzystującą lematy 2.1 oraz 2.2. Prawe strony produkcji rozpoczynających się od $v_1$ i $v_2$ 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 $v_3\to v_1{v}_2$. Usuwamy ją, a ponieważ prawa jej strona rozpoczyna się nieterminalem $v_1$, zastępujemy ten nieterminal prawą stroną produkcji $v_1\to v_2{v}_3$ i nowo otrzymaną produkcję $v_3\to v_2{v}_3{v}_2$ dodajemy do $P$. Ponieważ pierwszy nieterminal po prawej stronie ma niższy indeks niż 3, znowu stosujemy tę samą operację: usuwamy produkcję $v_3\to v_2{v}_3{v}_2$ i na jej miejsce wstawiamy produkcje powstałe w wyniku zastąpienia pierwszego $v_2$ z prawej jej strony łańcuchami $v_3{v}_1$ oraz $b$, czyli prawymi stronami produkcji, po których lewej stronie jest $v_2$. Otrzymujemy zatem dwie nowe produkcje: $v_3\to v_3{v}_1{v}_3{v}_2$ oraz $v_3\to b{v}_3{v}_2$. 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 $v_3\to v_3{v}_1{v}_3{v}_2$. Usuwamy ją z $P$ i w jej miejsce wstawiamy produkcje $v_3\to b{v}_3{v}_2{w}_3$, $v_3\to a{w}_3$, $w_3\to v_1{v}_3{v}_2{w}_3$.

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

$\begin{array}{rl}{v}_1& \to v_2{v}_3\\ v_2& \to v_3{v}_1|b\\ v_3& \to b{v}_3{v}_2{w}_3|a{w}_3|b{v}_3{v}_2|a\\ w_3& \to v_1{v}_3{v}_2|v_1{v}_3{v}_2{w}_3\end{array}$

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

$\begin{array}{rl}{v}_1& \to v_2{v}_3\\ v_2& \to b{v}_3{v}_2{w}_3{v}_1|a{w}_3{v}_1|b{v}_3{v}_2{v}_1|a{v}_1|b\\ v_3& \to b{v}_3{v}_2{w}_3|a{w}_3|b{v}_3{v}_2|a\\ w_3& \to v_1{v}_3{v}_2|v_1{v}_3{v}_2{w}_3\end{array}$

Prawymi stronami produkcji postaci $v_2\to x$ zastępujemy teraz nieterminale $v_2$ stojące jako pierwsze nieterminale po prawej stronie produkcji postaci $v_1\to v_{2}x$. W naszym przypadku jedyną taką produkcją jest produkcja $v_1\to v_2{v}_3$. Gramatyka wygląda teraz tak:

$\begin{array}{rl}{v}_1& \to b{v}_3{v}_2{w}_3{v}_1{v}_3|a{w}_3{v}_1{v}_3|b{v}_3{v}_2{v}_1{v}_3|a{v}_1{v}_3|b{v}_3\\ v_2& \to b{v}_3{v}_2{w}_3{v}_1|a{w}_3{v}_1|b{v}_3{v}_2{v}_1|a{v}_1|b\\ v_3& \to b{v}_3{v}_2{w}_3|a{w}_3|b{v}_3{v}_2|a\\ w_3& \to v_1{v}_3{v}_2|v_1{v}_3{v}_2{w}_3\end{array}$

Ostatecznie, po ukończeniu pętli, każda produkcja mająca po lewej stronie $v_1$, $v_2$ lub $v_3$ 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 $w_i$. Obie $w_3$-produkcje przekształcamy, zastępując pierwszy nieterminal stojący po ich prawych stronach (czyli $v_1$) prawymi stronami produkcji postaci $v_1\to x$. Obie $w_3$-produkcje zostaną z $P$ usunięte, a na ich miejsce dodane zostaną produkcje

$\begin{array}{lcl}{w}_3& \to & b{v}_3{v}_2{w}_3{v}_1{v}_3{v}_3{v}_2|a{w}_3{v}_1{v}_3{v}_3{v}_2|b{v}_3{v}_2{v}_1{v}_3{v}_3{v}_2\\ & & |a{v}_1{v}_3{v}_3{v}_2|b{v}_3{v}_3{v}_2\end{array}$

oraz

$\begin{array}{lcl}{w}_3& \to & b{v}_3{v}_2{w}_3{v}_1{v}_3{v}_3{v}_2{w}_3|a{w}_3{v}_1{v}_3{v}_3{v}_2{w}_3|b{v}_3{v}_2{v}_1{v}_3{v}_3{v}_2{w}_3\\ & & |a{v}_1{v}_3{v}_3{v}_2{w}_3|b{v}_3{v}_3{v}_2{w}_3\end{array}$

Ostatecznie, gramatyka w postaci Greibach ma postać:

$\begin{array}{lcl}{v}_1& \to & b{v}_3{v}_2{w}_3{v}_1{v}_3|a{w}_3{v}_1{v}_3|b{v}_3{v}_2{v}_1{v}_3|a{v}_1{v}_3|b{v}_3\\ v_2& \to & b{v}_3{v}_2{w}_3{v}_1|a{w}_3{v}_1|b{v}_3{v}_2{v}_1|a{v}_1|b\\ v_3& \to & b{v}_3{v}_2{w}_3|a{w}_3|b{v}_3{v}_2|a\\ w_3& \to & b{v}_3{v}_2{w}_3{v}_1{v}_3{v}_3{v}_2|a{w}_3{v}_1{v}_3{v}_3{v}_2|b{v}_3{v}_2{v}_1{v}_3{v}_3{v}_2\\ & & |a{v}_1{v}_3{v}_3{v}_2|b{v}_3{v}_3{v}_{2}b{v}_3{v}_2{w}_3{v}_1{v}_3{v}_3{v}_2{w}_3\\ & & |a{w}_3{v}_1{v}_3{v}_3{v}_2{w}_3|b{v}_3{v}_2{v}_1{v}_3{v}_3{v}_2{w}_3\\ & & |a{v}_1{v}_3{v}_3{v}_2{w}_3|b{v}_3{v}_3{v}_2{w}_3\end{array}$