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

% vim: spell spelllang=cs

\assignment{8}
\exercise{1}
\points{0,5}
\duedate{16. 4. 2023 23:59}

\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}
	Vedení FI se rozhodlo rekonstruovat celou budovu, a to od základů. Chtějí ji celou zbourat a místo ní postavit krásnou moderní budovu s novými posluchárnami, studentskými místnostmi a bazénem. Před tím, než budovu zbourají, dělníci musí z jednotlivých pater vyklidit věci. Aby toho nebylo málo, po rekonstrukci budovy musí věci vrátit na patra ve zpětném pořadí.

	\bigskip\noindent
	Dělníci tedy můžou: odnést věc z konkrétního patra ($o1,o2,o3$), přinést věc na konkrétní patro ($p1,p2,p3$) a rekonstruovat ($r$).

	\bigskip\noindent
	Dále musí platit:
	\begin{itemize}
		\item Rekonstrukce musí proběhnout právě jednou. A věci se můžou odnášet jenom do rekonstrukce a přinášet až po rekonstrukci.
		\item Všechny věci musí být přineseny v opačném pořadí, než v jakém byly odneseny. Jinými slovy: sklad, kde se dočasně ukládají věci, funguje jako zásobník.
		\item Z prvního patra není možné odnést 2 věci za sebou.
		\item Na druhém patře je nějaká věc, a tedy je potřeba ji určitě odnést.
	\end{itemize}

	Mějme tedy jazyk $L$ nad abecedou $\Sigma = \set{1, 2, 3, p, o, r}$, který popisuje všechny možné sekvence práce dělníků tak, aby rekonstrukce proběhla úspěšně.
	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.45\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $o2rp2$
				\item $o1o2o1rp1p2p1$
				\item $o1o2o3rp3p2p1$
			\end{itemize}
		\end{minipage}
		\begin{minipage}{0.45\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $o2o2rp2p2$
				\item $o3o2rp2p3$
				\item $o3o3o2rp2p3p3$
			\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.5\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $\eps$
				\item $o1o2rp2p1o2rp2$
				\item $o1o1o2rp2p1p1$
			\end{itemize}
		\end{minipage}
		\begin{minipage}{0.45\textwidth}
			\begin{itemize}\itemsep0pt\parskip0pt
				\item $o1o3rp3p1$
				\item $o1o2o3rp1p2p3$
				\item $p1p2o3rp3o2o1$
			\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/jaro2023/IB005/odp/du2023_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}
