\documentclass[12pt]{ib102}
\usepackage[czech]{babel}

\setassignment{8}
\setexercise{1}
\setduedate{30}{11}{2015}
\setpoints{2}


%%% ZDE NAPISTE SVOJE UCO, JMENO A SKUPINU
\setstudent{}
\setgroup{}
\setuco{}


\newcommand{\ttplus}{\mathbin{\texttt{+}}}
\newcommand{\ttminus}{\mathbin{\texttt{-}}}
\newcommand{\ttequals}{\mathbin{\texttt{=}}}

\begin{document}
\begin{zadani}
Uvažme abecedu $\Sigma = \set{a, \ttequals, \ttplus, \ttminus}$ a jazyk $L$ nad touto abecedou reprezentující sčítání a odečítání unárně zapsaných přirozených čísel bez nuly. 

Libovolné $n \in \mathbb{N}$ reprezentujeme jako posloupnost $a^n$. Tedy například číslo 3 bude reprezentováno jako $aaa$.

Slova z jazyka $L$ jsou tvaru
\[
a^{i_1} \pm_1 a^{i_2} \pm_2 \dots \pm_{n-1} a^{i_n} \ttequals z,
\]
kde $n \geq 1$, $\pm_k \in \set{\ttplus,\ttminus}$ pro všechna $0 < k < n$, $i_l > 0$ pro všechna $0 < l \leq n$ a $z$ je posloupnost znaků $a$ reprezentující výsledek operace.

Pro každé $0 < k < n$ označme jako $\odot_k$ aritmetickou operaci odpovídající symbolu $\pm_k$. Tedy pokud $\pm_k$ je $\ttplus$, pak $\odot_k$ je $+$, naopak pokud $\pm_k$ je $\ttminus$, pak $\odot_k$ je $-$.\footnote{Všimněte si rozdílu mezi syntaxí a sémantikou. Symbol $\ttplus$ je pouhý prvek z abecedy $\Sigma$ bez jakéhokoliv významu. Naproti tomu $+$ je standardní binární funkce, která pro dvě celá čísla vrátí jejich součet. Analogicky pro $\ttminus$ a $-$.} Označme dále jako $r_z$ celé číslo, které je výsledkem operací reprezentovaných částí slova před symbolem~$\ttequals$. Tedy $r_z = i_1 \odot_1 i_2 \odot_2 \dots \odot_{n-1} i_n$. Konečně, pokud $r_z \geq 0$, pak klademe $z = a^{r_z}$. Je-li naopak $r_z < 0$, klademe $z = \ttminus a^{-r_z}$.

\smallskip
\noindent
Uveďme konkrétní příklady slov z jazyka (mezery ve slově píšeme jen pro lepší čitelnost, nepatří mezi terminály):
\begin{itemize}
\item $aaa \ttequals aaa$,
\item $a \ttplus aa \ttminus a \ttequals aa$,
\item $a \ttminus a \ttequals {}$,
\item $a \ttminus aaaa \ttplus aa \ttequals \ttminus a$.
\end{itemize}

\noindent
Sestrojte (obyčejný, nikoli rozšířený)
nedeterministický zásobníkový automat akceptující jazyk $L$. Jasně uveďte, jakým 
způsobem váš automat akceptuje (koncovým stavem, prázdným zásobníkem).
\end{zadani}


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

\end{document}