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

% vim: fo+=t tw=80 spell spelllang=cs
% gen: ready

\assignment{6}
\exercise{1}
\points{2}
\duedate{7. 11. 2016}

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


\begin{document}
\begin{zadani}
Nechť $\Sigma = \set{\forall, \exists, \doteq, 1}$ je abeceda a $L$ je jazyk nad abecedou $\Sigma$ definovaný předpisem
$$L= \{ u\!\doteq\!1^m \mid u\in \{ \forall, \exists \}^*, \ m\in \mathbb{N}_0, \ \ \#_{\forall \exists}(u) \ + \ \#_{\exists \forall}(u) =m \},$$
kde $\#_{v}(u)$ značí počet výskytů řetězce $v$ v řetězci $u.$ 
\noindent
Jinými slovy, jazyk $L$ obsahuje všechny rovnosti tvaru $u\!\doteq\!1^m,$ kde počet alternací kvantifikátorů ve slově $u\in \{ \forall, \exists \}^*$ je roven $m,$ tj. počet kvantifikátorů ve slově $u,$ po nichž následuje jiný kvantifikátor, je $m.$ 

\bigskip\noindent
Příklady slov patřících do jazyka $L$:
$$\doteq,\quad \forall \!\doteq,\quad \forall\exists\!\doteq\!1,\quad
    \forall\forall\exists\!\doteq\!1,\quad
    \exists\forall\exists\!\doteq\!11,\quad \exists\forall\forall\forall\exists\exists\!\doteq\!11$$

\noindent
Příklady slov nenáležících do jazyka $L$:
$$\eps,\quad \forall\exists\!\doteq,\quad \forall\exists\!\doteq11,\quad \forall\exists\!\doteq\forall\exists\!\doteq\!1$$

\noindent
Sestrojte bezkontextovou gramatiku pro jazyk $L.$ Stručně, neformálně zdůvodněte, proč vaše gramatika generuje právě jazyk $L$.
\end{zadani}

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

\end{document}
