\documentclass{ib102}
\usepackage[shorthands=off,czech]{babel}

% vim: spell spelllang=cs
% gen: ready

\assignment{9}
\exercise{2}
\points{2}
\duedate{27. 11. 2017}

%%% ZDE NAPISTE SVOJE UCO A JMENO
\name{}
\uco{}


\begin{document}
\begin{zadani}
Uvažte následující gramatiku $G$:
\begin{alignat*}{3}
  G &= (\set{&&S, A, B, C, D, E}, \set{a, b}, P, S), \\
  P &= \{ &&S \to aB \mid bAb \mid Ab \mid AE, \\
  &	 &&A \to aBa \mid BS \mid Ca, \\
  &	 &&B \to \varepsilon \mid aB \mid aSb \mid bEE, \\
  &	 &&C \to aDC \mid Cb, \\
  &	 &&D \to \varepsilon \mid Ab \\
  &	 &&E \to \varepsilon \mid aAE \mid  bB \}.
\end{alignat*}

\noindent
Pomocí algoritmů z přednášky převeďte gramatiku $G$ na ekvivalentní vlastní gramatiku a následně na gramatiku v Chomského normální formě. Do~řešení uveďte celý postup převodu, zejména následující mezivýsledky:

\begin{enumerate}[a)]
    \item ke gramatice $G$ ekvivalentní gramatiku $G_1$ bez $\varepsilon$-pravidel (nezapomeňte uvést množinu $N_{\varepsilon}$ obsahující všechny neterminály, které se dají přepsat na $\varepsilon$),
    \item ke gramatice $G_1$ ekvivalentní gramatiku $G_2$ bez $\varepsilon$-pravidel a jednoduchých pravidel (uveďte množiny $N_{X}$, t.j. množiny všech neterminálů, na které se může $X \in N$ přepsat pomocí jednoduchých pravidel),
    \item ke gramatice $G_2$ ekvivalentní vlastní gramatiku $G_3$,
    \item ke gramatice $G_3$ ekvivalentní gramatiku $G_4$ v Chomského normální formě (CNF).
\end{enumerate}

\end{zadani}

\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
