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

% vim: spell spelllang=cs
% gen: ready

\assignment{9}
\exercise{2}
\points{2}
\duedate{25. 11. 2019}

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


\begin{document}
\begin{zadani}
\begin{enumerate}[a)]
    \item Uvažte následující gramatiku $G_1$:
    \begin{alignat*}{3}
        G_1 &= (\set{&&S, X, Y, Z}, \set{a, b, c}, P, S), \\
        P &= \set{ &&S \to YZ \mid aXZa, \\
        &    &&X \to YX \mid bY \mid aYZ, \\
        &    &&Y \to \varepsilon \mid c \mid YZ, \\
        &    &&Z \to a \mid Xb \mid \varepsilon \mid c }.       
    \end{alignat*}

    Pomocí algoritmů z přednášky převeďte gramatiku $G_1$ na ekvivalentní gramatiku bez $\varepsilon$-pravidel a následně z takto vzniklé gramatiky odstraňte jednoduchá pravidla. Do~řešení uveďte celý postup převodu, zejména:
    \begin{enumerate}[1.]
    \item ke gramatice $G_1$ 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^{''}_{1}$ bez $\varepsilon$-pravidel a jednoduchých pravidel (uveďte množiny $N_{A}$, t.j. množiny všech neterminálů, na které se může $A \in N$ přepsat pomocí jednoduchých pravidel).
    \end{enumerate} 
    \bigskip

    \item Uvažte následující gramatiku $G_2$:
    \begin{alignat*}{3}
        G_2 &= (\set{&&S, A, B, C, D, E}, \set{a, b, c}, P, S), \\
        P &= \set{ &&S \to Aa \mid a \mid Eb \mid abbc \mid aDD, \\
        &   &&A \to Aab \mid b \mid SEE \mid baD, \\
        &   &&B \to DaS \mid BaaC \mid a, \\
        &   &&C \to Da \mid a \mid bB \mid Db \mid SaD, \\
        &   &&D \to Da \mid DBc \mid bDb \mid DEaD, \\
        &   &&E \to Aa \mid a \mid bca }.
    \end{alignat*}

    Pomocí algoritmů z přednášky převeďte gramatiku $G_2$ 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:
    \begin{enumerate}[1.]
        \item ke gramatice $G_2$ ekvivalentní vlastní gramatiku $G^{'}_{2}$,
	    \item ke gramatice $G^{'}_{2}$ ekvivalentní gramatiku $G^{''}_{2}$ v Chomského normální formě (CNF).
    \end{enumerate}
\end{enumerate}
\end{zadani}

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

\end{document}
