\documentclass[a4paper]{article}
\begin{document}
Gramatika je \textit{Greibach} normalnoj formi ukoliko je
$\varepsilon$ slobodna i ukoliko joj je svako ne-$\varepsilon$
pravilo oblika $A\rightarrow a\alpha$, $a\in \Sigma$, $\alpha\in
N^*$

\begin{eqnarray*}
S&\rightarrow& Ba | Ab\\
A&\rightarrow& Sa | AAb | a\\
B&\rightarrow& Sb | BBa | b
\end{eqnarray*}
Oslobodimo se prvo leve rekurzije iz ove gramatike. U tom cilju
poredjajmo neterminale kao ${S,A,B}$. $S$ nema direktne leve
rekurzije, tako da u prvom koraku nema izmena. Zatim prelazimo na
$A$. Zamenom $S$-a svojim desnim stranama dobijamo

\begin{eqnarray*}
S&\rightarrow& Ba | Ab\\
A&\rightarrow& Baa | Aba | AAb | a\\
B&\rightarrow& Sb | BBa | b
\end{eqnarray*}

Oslobodimo se sada neposredne leve rekurzije iz
$$
A\rightarrow Aba | AAb | Baa | a\\
$$


\begin{eqnarray*}
S&\rightarrow& Ba | Ab\\
A&\rightarrow& Baa | a | BaaA' | aA'\\
A'&\rightarrow& ba | Ab | baA' | AbA'\\
B&\rightarrow& Sb | BBa | b
\end{eqnarray*}

Predjimo sada na neterminal $B$. Zamenimo najpre $S$ svojim desnim
stranama

\begin{eqnarray*}
S&\rightarrow& Ba | Ab\\
A&\rightarrow& Baa | a | BaaA' | aA'\\
A'&\rightarrow& ba | Ab | baA' | AbA'\\
B&\rightarrow& Bab | Abb | BBa | b
\end{eqnarray*}

Zamenimo sada $A$ svojim desnim stranama

\begin{eqnarray*}
S&\rightarrow& Ba | Ab\\
A&\rightarrow& Baa | a | BaaA' | aA'\\
A'&\rightarrow& ba | Ab | baA' | AbA'\\
B&\rightarrow& Bab | Baabb | abb | BaaA'bb | aA'bb | BBa | b
\end{eqnarray*}

Oslobodimo se sada neposredne leve rekurzije iz
$$
B\rightarrow Bab | Baabb | BaaA'bb | BBa | abb |  aA'bb | b
$$

\begin{eqnarray*}
S&\rightarrow& Ba | Ab\\
A&\rightarrow& Baa | a | BaaA' | aA'\\
A'&\rightarrow& ba | Ab | baA' | AbA'\\
B&\rightarrow&  abb |  aA'bb | b | abbB' |  aA'bbB' | bB' \\
B'&\rightarrow& ab | aabb | aaA'bb | Ba |abB' | aabbB' | aaA'bbB'
| BaB'
\end{eqnarray*}

Defini\v simo sada na slede\' ci na\v cin poredak medju
neterminalima. Ukoliko postoji pravilo $A\rightarrow B \alpha$
onda je $A<B$. Ovo defini\v se parcijalni poredak medju
neterminalima koji se mo\v ze pro\v siriti do linearnog. U na\v
soj gramatici se to mo\v ze uraditi ovako
$$B<B'<A<A'<S$$
Imaju\' ci ovaj poredak u vidu sti\v zemo do gramatike u kojoj
svako pravilo po\v cinje terminalom. Zatim koriste\' ci "trik"
uvodjenja novih neterminala dobijamo gramatiku u GNF
\begin{eqnarray*}
B&\rightarrow&  ab'b' |  aA'b'b' | b | ab'b'B' |  aA'b'b'B' | bB' \\
B'&\rightarrow& ab' | aa'b'b' | aa'A'b'b' | ab'B' | aa'b'b'B' | aa'A'b'b'B' |\\
&&ab'b'a' |  aA'b'b'a'a' | ba' | ab'b'B'a' |  aA'b'b'B'a' | bB'a'a'B'| \\
&&ab'b'a'B' |  aA'b'b'a'B' | ba'B' | ab'b'B'a'B' |  aA'b'b'B'a'B' | bB'a'B'\\
A&\rightarrow&   a | aA'|\\
&&ab'b'a'a' |  aA'b'b'a'a' | ba'a' | ab'b'B'a'a' |  aA'b'b'B'a'a' | bB'a'a' |\\
&& ab'b'a'a'A' |  aA'b'b'a'a'A' | ba'a'A' | ab'b'B'a'a'A' |  aA'b'b'B'a'a'A' | bB'a'a'A'\\
A'&\rightarrow& ba' | ba'A' |\\
&&ab' | aA'b'|\\
&&ab'b'a'a'b' |  aA'b'b'a'a'b' | ba'a'b' | ab'b'B'a'a'b' |  aA'b'b'B'a'a'b' | bB'a'a'b' |\\
&& ab'b'a'a'A'b' |  aA'b'b'a'a'A'b' | ba'a'A'b' | ab'b'B'a'a'A'b' |  aA'b'b'B'a'a'A'b' | bB'a'a'A'b'|\\
&& ab'A' | aA'b'A'|\\
&&ab'b'a'a'b'A' |  aA'b'b'a'a'b'A' | ba'a'b'A' | ab'b'B'a'a'b'A' |  aA'b'b'B'a'a'b'A' | bB'a'a'b'A' |\\
&& ab'b'a'a'A'b'A' |  aA'b'b'a'a'A'b'A' | ba'a'A'b'A' |\\&&
ab'b'B'a'a'A'b'A' |  aA'b'b'B'a'a'A'b'A' | bB'a'a'A'b'A'b'A'\\
S&\rightarrow& ab'b'a' |  aA'b'b'a' | ba' | ab'b'B'a' |  aA'b'b'B'a' | bB'a' |\\
&& ab' | aA'b'|\\
&&ab'b'a'a'b' |  aA'b'b'a'a'b' | ba'a'b' | ab'b'B'a'a'b' |  aA'b'b'B'a'a'b' | bB'a'a'b' |\\
&& ab'b'a'a'A'b' |  aA'b'b'a'a'A'b' | ba'a'A'b' | ab'b'B'a'a'A'b'
| aA'b'b'B'a'a'A'b' | bB'a'a'A'b'\\
a'&\rightarrow& a\\
b'&\rightarrow& b
\end{eqnarray*}

Kao \v sto se da videti ovaj algoritam vodi re\v senju koje ima
previ\v se pravila. Zato uradimo isti ovaj zadatak na drugi na\v
cin. Zapi\v simo prvo polaznu gramatiku u matri\v cnom obliku
$$
[S,A,B]=[S,A,B]\left[\begin{array}{ccc}
  \emptyset & a & b \\
  b & Ab & \emptyset \\
  a & \emptyset & Ba \\
\end{array}\right]+[\emptyset,a,b]
$$

Uvodjenjem novih neterminala $N_{ij}$ oslobodimo se leve rekurzije
u matri\v cnom obliku

$$
[S,A,B]=[\emptyset,a,b]+[\emptyset,a,b]\left[\begin{array}{ccc}
  N_{11} & N_{12} & N_{13}\\
  N_{21} & N_{22} & N_{23}\\
  N_{31} & N_{32} & N_{33}\\
\end{array}\right]
$$

$$
\left[\begin{array}{ccc}
  N_{11} & N_{12} & N_{13}\\
  N_{21} & N_{22} & N_{23}\\
  N_{31} & N_{32} & N_{33}\\
\end{array}\right]=\left[\begin{array}{ccc}
  \emptyset & a & b \\
  b & Ab & \emptyset \\
  a & \emptyset & Ba \\
\end{array}\right]+\left[\begin{array}{ccc}
  \emptyset & a & b \\
  b & Ab & \emptyset \\
  a & \emptyset & Ba \\
\end{array}\right]\left[\begin{array}{ccc}
  N_{11} & N_{12} & N_{13}\\
  N_{21} & N_{22} & N_{23}\\
  N_{31} & N_{32} & N_{33}\\
\end{array}\right]
$$

tj. u razvijenom obliku

\begin{eqnarray*}
S&\rightarrow&aN_{21} | bN_{31}\\
A&\rightarrow&a| aN_{22} | bN_{32}\\
B&\rightarrow&b| aN_{23} | bN_{33}\\
N_{11}&\rightarrow& aN_{21} | bN_{31}\\
N_{12}&\rightarrow& a | aN_{22} | bN_{32}\\
N_{13}&\rightarrow& b | aN_{23} | bN_{33}\\
N_{21}&\rightarrow& b | bN_{11} | AbN_{21}\\
N_{22}&\rightarrow& Ab | bN_{12} | AbN_{22}\\
N_{23}&\rightarrow& bN_{13} | AbN_{23}\\
N_{31}&\rightarrow& a | aN_{11} | BaN_{31}\\
N_{32}&\rightarrow& aN_{12} | BaN_{32}\\
N_{33}&\rightarrow& Ba | aN_{13} | BaN_{33}\\
\end{eqnarray*}

Uvr\v s\' cavanjem desnih strana pravila za neterminale $A$ i $B$
i kori\v s\' cenjem "trika" kojim od terminala "pravimo"
neterminale GNF trivijalno sledi

\begin{eqnarray*}
S&\rightarrow&aN_{21} | bN_{31}\\
A&\rightarrow&a | aN_{22} | bN_{32}\\
B&\rightarrow&b | aN_{23} | bN_{33}\\
N_{11}&\rightarrow& aN_{21} | bN_{31}\\
N_{12}&\rightarrow& a | aN_{22} | bN_{32}\\
N_{13}&\rightarrow& b | aN_{23} | bN_{33}\\
N_{21}&\rightarrow& b | bN_{11} | ab'N_{21} | aN_{22}b'N_{21} | bN_{32}b'N_{21}\\
N_{22}&\rightarrow& ab'| aN_{22}b' | bN_{32}b' | bN_{12} | ab'N_{22} | aN_{22}b'N_{22} | bN_{32}b'N_{22}\\
N_{23}&\rightarrow& bN_{13} | ab'N_{23} | aN_{22}b'N_{23} | bN_{32}b'N_{23}\\
N_{31}&\rightarrow& a | aN_{11} | ba'N_{31} | aN_{23}a'N_{31} | bN_{33}a'N_{31}\\
N_{32}&\rightarrow& aN_{12} | bN_{32} | aN_{23}N_{32} | bN_{33}a'N_{32}\\
N_{33}&\rightarrow& ba' | aN_{23}a' | bN_{33}a' | aN_{13} | ba'N_{33} | aN_{23}a'N_{33} | bN_{33}a'N_{33}\\
a'&\rightarrow& a\\
b'&\rightarrow& b
\end{eqnarray*}



\end{document}
