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

\assignment{6}
\exercise{2}
\points{0,5}
\duedate{4. 4. 2022 12:00}

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


\begin{document}
\begin{zadani}
    Nechť $L$ je libovolný jazyk nad abecedou $\Sigma=\set{a,b,c}$.

    \noindent
    Mějme operaci $\mathit{EvenCensor}()$ takovou, že jazyk $R = \mathit{EvenCensor}(L)$ obsahuje pro každé slovo $w \in L$ modifikované slovo $w'$ vzniklé tak, že každé druhé písmeno slova $w$ nahradíme za $\#$.

    Formálně definujeme operaci následovně (použijeme pomocnou operaci $\mathit{wEvenCensor}()$ operující nad slovy):
    \begin{align*}
    \mathit{wEvenCensor}(\eps) &= \eps \\
    \mathit{wEvenCensor}(d) &= d  &&\text{pro } d \in \Sigma\\
    \mathit{wEvenCensor}(dew) &= d \cdot \# \cdot \mathit{wEvenCensor}(w)  &&\text{pro } d,e \in \Sigma, w \in \Sigma^* &
    \end{align*}
    \begin{align*}
    \mathit{EvenCensor}(L) &= \set{ \mathit{wEvenCensor}(w) \mid w \in L}
    \end{align*}

    \medskip\noindent
    Například tedy:
    \begin{align*}
    \mathit{EvenCensor}(\set{a, b, c}) &= \set{a, b, c} \\
    \mathit{EvenCensor}(\set{ab, a}) &= \set{a\#, a} \\
    \mathit{EvenCensor}(\emptyset) &= \emptyset \\
    \mathit{EvenCensor}(\set{\eps}) &= \set{\eps} \\
    \mathit{EvenCensor}(\set{aba, aca, bacabac, abcc}) &= \set{a\#a, b\#c\#b\#c, a\#c\#} \\
    \mathit{EvenCensor}(\Sigma^*) &= \set{a\#,b\#,c\#}^* \cdot \set{\eps,a,b,c} &&
    \end{align*}
    
    \medskip \noindent
    Vaším úkolem je rozhodnout, zda pro každý regulární jazyk $L$ je jazyk $\mathit{EvenCensor}(L)$ taktéž regulární. Tedy zda je třída regulárních jazyků uzavřená na operaci $\mathit{EvenCensor}()$. Uveďte vaše rozhodnutí a odpověď dokažte, a to tak, že:
    \begin{itemize}
            \item Pokud rozhodnete, že třída regulárních jazyků není uzavřená na operaci $\mathit{EvenCensor}()$, najděte regulární jazyk $L$ takový, že jazyk $\mathit{EvenCensor}(L)$ regulární není. Neregularitu jazyka $\mathit{EvenCensor}(L)$ dokažte buď odvoláním se na známé neregulární jazyky, nebo pomocí obměny lemmatu o vkládání (Pumping lemma), nebo použitím Myhillovy-Nerodovy věty.
            \item Pokud rozhodnete, že je, dokažte tvrzení například s pomocí známých uzávěrových vlastností třídy regulárních jazyků prezentovaných na přednášce, nebo konstruktivně popsáním algoritmu na transformaci nějakého formalizmu pro popis regulárních jazyků (například transformací automatu pro jazyk $L$ na automat pro jazyk $\mathit{EvenCensor}(L)$). Správnost vašeho algoritmu nemusíte dokazovat.
    \end{itemize}

    \medskip\noindent
    {\small \textit{Poznámka: Pokud píšete řešení v \TeX{}u, před odevzdáním prosím odmažte zadání.}}
\end{zadani}
\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
