\documentclass[12pt]{ib102}
\usepackage[czech]{babel}

\setassignment{7}
\setexercise{1}
\setduedate{10}{11}{2014}
\setpoints{2}

%%% ZDE NAPISTE SVOJE UCO, JMENO A SKUPINU
\setstudent{}
\setgroup{}
\setuco{}


\begin{document}
\begin{zadani}
Uvažte následující gramatiku $G$:
\begin{alignat*}{3}
  G &= (\set{&&S, A, B, C}, \set{a, b}, P, S), \\
  P &= \{ &&S \to A \mid SabB \mid C, \\
  &	 &&A \to \varepsilon \mid AaS, \\
  &	 &&B \to b \mid AA, \\
  &	 &&C \to aS  \}.
\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}
