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

\setassignment{5}
\setexercise{1}
\setduedate{20}{10}{2014}
\setpoints{2}

%%@HEADER@%%

\begin{document}
\begin{zadani}
    Rozhodněte a dokažte, zda je třída regulárních jazyků nad abecedou
    \mbox{$\Sigma = \set{ a, b, c }$} uzavřena na unární operaci $\mathit{zlibovolni}$:
\begin{align*}
    \mathit{zlibovolni}(L) = \{ u_1^{i_1} u_2^{i_2}\ldots{}u_n^{i_n}
        \mid{} &{}n \in \mathbb{N}_0
        \land u_1, u_2,\ldots, u_n \in \Sigma \\
        & {}\land u_1u_2 \ldots u_n \in L
        \land i_1,\ldots,i_n \in \mathbb{N} \}
\end{align*}

\noindent
Tedy, intuitivně řečeno, jazyk $\mathit{zlibovolni}(L)$ obsahuje všechna
slova z jazyka $L$ a navíc všechna slova, která z nich vzniknou tak, že 
tak, že každé písmeno ve slově $w \in L$ libovolněkrát za sebou zopakujeme
(nikoliv však odstraníme).
Speciálně pak $\eps \in \mathit{zlibovolni}(L)$ právě tehdy, když $\eps \in L$.

\bigskip\noindent
Uveďme ještě příklady:
\begin{align*}
\mathit{zlibovolni}( \set{ c, ab } ) &= \set{c}^+ \cup \set{a}^+\cdot\set{b}^+ \\
    &= \set{ c, ab, cc, aab, abb, ccc, aaab, aabb, abbb, cccc, \ldots } \\
\mathit{zlibovolni}( \set{ \eps, abc } ) &= \set{ \eps } \cup \set{a}^+   \cdot \set{b}^+ \cdot \set{c}^+ \\
    &= \set{ \eps, abc, aabc, abbc, abcc, aabbc, aabcc, abbcc, \ldots }\\
\mathit{zlibovolni}( \set{a}^* \cdot \set{b}^* \cdot \set{a} ) &= \set{a}^*\cdot\set{b}^*\cdot\set{a}^+
\end{align*}

\medskip\noindent
\textit{Nápověda:} Pokud rozhodnete, že třída regulárních jazyků není
uzavřená na operaci $\mathit{zlibovolni}$, uveďte příslušný protipříklad. Pokud
rozhodnete, že třída regulárních jazyků je uzavřená na operaci
$\mathit{zlibovolni}$, musíte toto tvrzení dokázat, například s pomocí známých
uzávěrových vlastností třídy regulárních jazyků, nebo konstruktivně
popsáním algoritmu na transformaci nějakého formalizmu pro popis
regulárních jazyků.
\end{zadani}

%%@FOOTHER@%%
\end{document}
