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

% vim: spell spelllang=cs
% gen: ready

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

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


\begin{document}
	\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 pro libovolné $n$ vygenerovat slovo, které obsahuje alespoň $n$ symbolů $a$. Výstupem algoritmu tedy bude množina neterminálů
		\[N_a = \left \{ X \in N \mid \forall n \exists w\in\Sigma^*. X \Rightarrow^* w \land \#_a(w) \geq n \right \}.\]
		
		\bigskip
		\noindent
		Příklad gramatiky:
	    \[ G = (\set{D, A, B, E, F, G}, \set{a, b, c}, P, D) \]
		\begin{align*}
	    P = \{ D &\to DAab \mid \eps, &
	    A &\to \eps \mid bc \mid BB, \\
	    B &\to aBc, &
	    E &\to bF \mid ca, \\
	    F &\to Ga \mid b, &
	    G &\to bF \}
	    \end{align*}
        Korektní výstup algoritmu pro ni: $N_a = \{D, E, F, G\}$.
		
		\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}
