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

% vim: spell spelllang=cs

\assignment{8}
\exercise{1}
\points{0,5}
\duedate{19. 4. 2022 12:00}
\definecolor{medium-blue}{rgb}{0,0,0.5}
\usepackage[urlcolor={medium-blue}, colorlinks=true]{hyperref}

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


\begin{document}
\begin{zadani}
	Blíží se Velikonoce a informatik se rozhodl, že své blízké obdaruje velikonočními vejci. Aby tak mohl učinit, musí vejce nejdříve koupit. Může se však také rozhodnout, že místo toho, aby koupená vejce někomu daroval, sám je sní. Nicméně protože je informatik štědrý, rozhodl se, že alespoň jedno koupené vejce někomu daruje. 

	\bigskip\noindent
	Informatik tedy může velikonoční vejce: koupit ($k$), sníst ($s$) a darovat ($d$).
	
	\bigskip\noindent
	Dále musí platit:
	\begin{itemize}
		\item S velikonočním vejcem se může provádět cokoli dalšího až potom, co jej informatik koupí.
		\item Informatik se může rozhodnout, jestli vejce sní, nebo daruje. Maximálně se však toto rozhodnutí týká jen tolika vajec, kolik jich má aktuálně koupených.
		\item Alespoň jedno vejce musí darovat, ale nemusí to nutně být první akce, kterou s vejci provede -- může sníst libovolné množství koupených vajec předtím, než se rozhodne nějaké darovat.
		\item Informatik musí spotřebovat všechna zakoupená vejce, tedy po Velikonocích mu žádné nezůstanou doma.
	\end{itemize}
	
	Mějme tedy jazyk $L$ nad abecedou $\Sigma = \set{d, k, s}$, který popisuje všechny možné sekvence akcí, které může informatik s vejci dělat.
	Slova tohoto jazyka jsou tedy sekvence akcí, které splňují výše popsané podmínky, kde vlevo je ta nejstarší akce a vpravo ta nejnovější akce.
	
	\bigskip\noindent
	\begin{minipage}{0.49\textwidth}
		\noindent Příklady slov patřících do jazyka $L$:
		
		\medskip\noindent
		\begin{minipage}{0.23\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $kd$
				\item $kskd$
				\item $kdks$
			\end{itemize}
		\end{minipage}
		\begin{minipage}{0.28\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $kksd$
				\item $kkds$
				\item $kkddks$
			\end{itemize}
		\end{minipage}
		\begin{minipage}{0.45\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
                                \item $kkkssd$
                                \item $kksskd$
                                \item $kkkssksd$
			\end{itemize}
		\end{minipage}
	\end{minipage}
	\hfill
	\begin{minipage}{0.49\textwidth}
		\noindent Příklady slov nepatřících do jazyka $L$:
		
		\medskip\noindent
		\begin{minipage}{0.23\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $\eps$
				\item $ksd$
				\item $dks$
			\end{itemize}
		\end{minipage}
		\begin{minipage}{0.71\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $ksk$
				\item $ksdk$
				\item $kkdsk$
			\end{itemize}
		\end{minipage}
	\end{minipage}
	
	\bigskip\noindent
	Vaším úkolem je sestrojit bezkontextovou gramatiku, která generuje jazyk $L$. (Gramatika může, ale nemusí obsahovat epsilon pravidla.)
	
	
\end{zadani}

\begin{reseni}
Tento úkol je automaticky vyhodnocován podobně jako některé úkoly na regulární jazyky.
Úkol se odevzdává v ISu přes odpovědník
\uv{\href{https://is.muni.cz/auth/el/fi/jaro2022/IB005/odp/du2022_0801.qref}{DÚ
odevzdávání: úkol 08, příklad 1},} v něm však nenajdete žádné další informace k
tomuto úkolu, doporučujeme jej tedy otevírat až po vyřešení úkolu.

\paragraph{Formát zápisu řešení} je obdobný jako u odpovědníků na konstrukci
regulárních gramatik, zapisujete však samozřejmě gramatiku bezkontextovou. I
tento formát je popsán na webu vyhodnocovací služby –
\url{https://fja.fi.muni.cz/reg/userref}. Syntaktické korektnosti prosím věnujte
zvýšenou pozornost, u bezkontextových gramatik bohužel nemáme k dispozici
kontrolu syntaxe.

\bigskip\noindent
Případné dotazy k formalismu zápisu prosím směřujte do diskusního fóra.
\end{reseni}

\end{document}
