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

% vim: spell spelllang=cs

\assignment{8}
\exercise{2}
\points{0,5}
\duedate{15. 4. 2024 12:00}

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


\begin{document}

%%@ASSIGNMENT@%%

\begin{zadani}
    Nechť $\Sigma = \set{a,b,c}$.
    Napište algoritmus, který pro zadanou bezkontextovou gramatiku $\mathcal{G}=(N,\Sigma,P,S)$ spočítá množinu všech neterminálů takových, že z každého z nich lze vygenerovat slovo, které obsahuje sudý (párny) počet symbolů $a$. Výstupem algoritmu tedy bude množina neterminálů
    \[N_{2a} = \{ X \in N \mid \exists w \in \Sigma^*. X \Rightarrow^* w \land 2 \mid \#_a(w) \}.\]

    \bigskip
    \noindent
    Příklad gramatiky:
    \[ G = (\set{D, A, B, C, E, F}, \set{a, b, c}, P, D) \]
    \begin{align*}
    P = \{ D &\to Bc \mid acC, &
    A &\to aa \mid \eps, \\
    B &\to aAb \mid abc, &
    C &\to aB \mid c, \\
    E &\to BE \mid b, &
    F &\to FFA \mid a \}
    \end{align*}
    Korektní výstup algoritmu pro ni: $N_{2a} = \{A, C, E, F\}$.

    \bigskip
    \noindent
    Popište princip fungování vašeho algoritmu a dokažte, že je tento algoritmus konvergentní (vždy skončí). Můžete využívat libovolné algoritmy z~přednášky, musíte na to však upozornit v~textu.
\end{zadani}

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