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

% vim: spell spelllang=cs

\assignment{9}
\exercise{1}
\points{0,5}
\duedate{25. 4. 2022 12:00}

%%% 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{&&X, A, B, F}, \set{m, a, j}, P_{1}, X), \\
            P_{1} &= \set{ &&X \to FF \mid Baj \mid jA \mid FaX, \\
            &    &&A \to FFA \mid AjAj \mid aj, \\
            &    &&B \to mAj \mid BaF \mid FX, \\
            &    &&F \to \eps \mid FjA}.
        \end{alignat*}

        Pomocí algoritmů z přednášky převeďte gramatiku $G_1$ na jazykově 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$ jazykově 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}$ jazykově ekvivalentní gramatiku $G^{''}_{1}$ 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).
        \end{enumerate}
        \bigskip

        \item Uvažte následující gramatiku $G_2$:
        \begin{alignat*}{3}
            G_2 &= (\set{&&K, M, O, I}, \set{t, u, r}, P_{2}, K), \\
            P_{2} &= \set{ &&K \to OtrOK \mid OtOK \mid rtut, \\
            &   &&M \to Krt \mid KrIK \mid IM, \\
            &   &&O \to KrOK \mid tur \mid tOM, \\
            &   &&I \to trIK \mid MOK }.
        \end{alignat*}

        Pomocí algoritmů z přednášky převeďte gramatiku $G_2$ na jazykově 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$ jazykově ekvivalentní vlastní gramatiku $G^{'}_{2}$,
            \item ke gramatice $G^{'}_{2}$ jazykově ekvivalentní gramatiku $G^{''}_{2}$ v Chomského normální formě (CNF).
        \end{enumerate}
    \end{enumerate}
   \bigskip\noindent
	\textit{Poznámka: Pokud píšete řešení v \TeX u, před odevzdáním prosím odmažte zadání. }
\end{zadani}

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

\end{document}
