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

% vim: spell spelllang=cs
% gen: ready

\assignment{9}
\exercise{2}
\points{2}
\duedate{26. 11. 2018}

%%% 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, F}, \set{a, b, c}, P, S), \\
P &= \{ &&S \to CB \mid cab, \\
&	 &&A \to \varepsilon \mid EbD \mid aa, \\
&	 &&B \to A \mid Cb \mid b, \\
&	 &&C \to \varepsilon \mid BbA, \\
&	 &&D \to aaaD \mid aaa \mid \varepsilon, \\
&	 &&E \to aE \mid bFa \mid  aDF \mid bDE,\\
&	 &&F \to bEaa \mid Fa \}.
\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}
