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

% vim: spell spelllang=cs
% gen: ready

\assignment{8}
\exercise{1}
\points{2}
\duedate{18. 11. 2019}

\newcommand{\up}{\nearrow}
\newcommand{\dn}{\searrow}

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

\begin{document}
\begin{zadani}
Uvažme trasy popsané pomocí úseků stoupání ($\up$) a klesání ($\dn$); příkladem trasy může být: $\up \up \up \dn \dn \up$. Ke každé trase chceme mít informaci o počtu extrémů na této trase (vrcholů a údolí; v našem příkladu jsou 2 extrémy). Počet extrémů chceme vyjádřit počtem znaků $e$ a vytvořit rovnost $\textit{trasa} \approx \textit{odpovídající počet e}$. Správně utvořené rovnosti budou odpovídat právě slovům jazyka $L$.

\medskip
Formálněji je $L$ jazyk slov nad abecedou $\Sigma = \{ \up, \dn, \approx, e \} $ ve tvaru $\{ \up, \dn \}^* \cdot \{\approx\} \cdot \{ e \}^*$
kde počet podslov $\up \dn$ a $\dn \up$ (vrcholů a údolí) na levé straně znaku $\approx$ odpovídá počtu $e$ (extrémů) na jeho pravé straně.

\bigskip

\noindent
\begin{minipage}{0.5\textwidth}
\noindent Příklady slov patřících do jazyka:
\begin{itemize}\itemsep0pt
    \item $\up \up \up \dn \approx{} e$
    \item $\up \up \up \up \approx{}$
    \item $\approx{}$
    \item $\dn\approx{}$
    \item $\dn \up \dn\approx{}ee$
    \item $\up \up \up \dn \dn \up \approx{} ee$
\end{itemize}
\end{minipage}
\begin{minipage}{0.48\textwidth}
\noindent Příklady slov nepatřících do jazyka:
\begin{itemize}\itemsep0pt
    \item $\up \dn \dn \approx{} $
    \item $\up \up  $
    \item $e$
    \item $\dn \up \dn\approx{}e$
    \item $\approx{}e$
    \item ${\approx{}}{\approx{}}$
\end{itemize}
\end{minipage}

\bigskip\noindent
Navrhněte bezkontextovou gramatiku, která generuje právě všechna slova jazyka $L$ (tedy správně vytvořené rovnosti).
\end{zadani}
\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
