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

% vim: fo+=t tw=80 spell spelllang=cs
% gen: ready

\assignment{7}
\exercise{1}
\points{2}
\duedate{14. 11. 2016}

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


\begin{document}
\begin{zadani}
Uvažte následující gramatiku $G$:
\begin{alignat*}{3}
  G &= (\set{&&S, B, C, D, E}, \set{a, b, c}, P, S), \\
  P &= \{ &&S \to cSCb \mid aB \mid D, \\
  &	 &&B \to CB \mid aEB, \\
  &	 &&C \to Bab \mid Sa, \\
  &	 &&D \to aS \mid a \mid \varepsilon \\
  &	 &&E \to b \mid  \varepsilon, \}.
\end{alignat*}

\noindent
Pomocí algoritmů z přednášky převeďte gramatiku $G$ na ekvivalentní 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),
  \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}
