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

% vim: spell spelllang=cs

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

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


\begin{document}
\begin{zadani}
Uvažte následující gramatiku $G_{1}$:
	\begin{align*}
	G_{1} = (&\set{1, 0, 2, 3, 4, 5, 6, 7}, \set{+, -, *, /, s}, P_{1}, 1) \\
	P_{1} = \{ &1 \to + \mid - \mid 1+2 \mid +3, \\
	&0 \to 0+{} \mid 0 - 3 \mid + \mid {}+4, \\
	&2 \to s2 \mid s \mid 7*7, \\
	&3 \to 4 - s \mid {}+4, \\
	&4 \to {}+3s \mid 335, \\
	&5 \to 1/0 \mid 0/0 \mid s1s , \\
	&6 \to +- \mid 666, \\
	&7 \to {}*0+{} \mid 1+2 \mid 42\}
	\end{align*}
	Uveďte ekvivalentní redukovanou gramatiku $G_{2}$ včetně postupu, jak jste k ní došli.\\
	
\medskip\noindent
Následně uvažte gramatiku $G_{3}$:
	\begin{align*}
	G_{3} = (&\set{B, R, N, O}, \set{a, d, k, z}, P_{3}, B) \\
	P_{3} = \{ &B \to dRak \mid  BaR \mid  RaNO \mid  NOk, \\
	&R \to BRak \mid  daR \mid  kaz, \\
	&N \to kaR \mid  ROk, \\
	&O \to NORa \mid  a \mid  OkO\}
	\end{align*}
	Pomocí algoritmu z přednášky zkonstruujte ke gramatice $G_{3}$ ekvivalentní nelevorekurzivní gramatiku $G_4$. Uveďte, jaké uspořádání neterminálů jste zvolili při odstraňování nepřímé levé rekurze a rovněž uveďte celý postup převodu. Úprava nemá vést k více než 20 pravidlům u kteréhokoli z neterminálů.
\end{zadani}

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

\end{document}
