\documentclass[a4paper]{article}
\usepackage[slovak]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{color}
\usepackage{multicol}
\usepackage{ wasysym }


\def\skok{{}{\hspace{1cm}}}
\RequirePackage{amssymb}

% FoJa Definicie ZACIATOK %
\def\eps{\varepsilon}
\def\N{\mathbb{N}}
\def\Lcf{\mathscr{L}_{\it CF}}
\def\R{{\cal R}}
\def\Lre{\mathscr{L}_{\it RE}}
\def\Lrec{\mathscr{L}_{\it rec}}
\def\Lecs{\mathscr{L}_{\it ECS}}
\def\Ldpda{\mathscr{L}_{\it DPDA}}
\def\Ledpda{\mathscr{L}_{\it eDPDA}}

\def\kodTS#1{ \langle #1 \rangle}
\def\blank{{\bf B}}
\def\pseudoBlank{\overline{B}}

\def\domino#1#2{\begin{tabular}{|c|}\hline #1 \\\hline #2\\ \hline\end{tabular}}

\def\to{\rightarrow}
\def\compStep#1{\vdash_{#1}}
\def\compStepIt#1{\vdash^*_{#1}}
% FoJa Definicie KONIEC %


\begin{document}

\centerline{\Large\sc Sada úloh na cvičenie 2}
\bigskip
\hrule
\bigskip

\centerline{\bf Pokyny (pre všetky úlohy na FoJa II):}
Očakáva sa, že všetky vaše tvrdenia a závery, ktoré neboli dokázané na prednáške poriadne dokážete. Miera formalizma sa očakáva zhruba taká, ako ku koncu semestra FoJa I a ako budete vidieť na prednáške. Ťažko napísať presné pravidlá čo je ešte poriadny dôkaz a čo je už odfláknuté, ale dobré pravidlo palca na ruke (doslovný preklad z rule of thumb) je, že technické indukcie pri konštrukciách netreba robiť a zvyšok treba robiť.


\bigskip
\hrule
\bigskip



\begin{enumerate}

\item
K jazyku $L = \{ awa ~|~ w \in \{a,b\}^*;~ \#_a(w) \equiv 1 \pmod{2} \} \cup \{ b^{2k} ~|~ k > 1 \}$ nad $\Sigma = \{a,b\}$ vieme podľa Myhill-Nerodeovej
vety zostrojiť reláciu ekvivalencie $R_L$ na slovách z $\{a,b\}^*$ ktorá je konečného indexu. Nájdite jej jednotlivé triedy ekvivalencie.
 
\item
Pomocou Myhill-Nerodeovej vety dokážte, že jazyk 
$L = \{ a^{i}b^{j} ~|~ i \geq j\}$ nie je regulárny.

\item
Zostrojte minimálny DKA pre jazyk
$L = \{bba^{k+1}bu ~|~ k \in \N ;~ u \in \{a,b\}^*;~ \#_a(u) \mbox { mod } 2 = k \mbox{ mod } 3 \}$. Slovne zdôvodnite, že vami zostrojený DKA je správny. Formálne dokážte, že je minimálny.

\item
Nech $L = \{a^nca^n ~|~ n > 0\}$. Zostrojte a-prekladač $M$ taký, že $M(L) = \{ a^nb^{2n+3} ~|~ n > 1\}$.

\item
Nech $L = \{cacwc^{4k} ~|~ k \in \N ;~ w \in \{a,b\}^*;~ \#_a(w) = \#_b(w) \}$. Zostrojte a-prekladač $M$ taký, že $M(L) = \{ a^nb^{2k+3} ~|~ n,k \in \N \}$.

\item Zostrojte a-prekladač $M$ taký, že pre ľubovolný jazyk $L$ nad abecedou $\Sigma = \{a,b\}$ bude platiť $M(L) = Suffix(L)$, kde $Suffix(L) = \{w ~|~ \exists u, ~ uw \in L\}$.

\item
Pomocou a-prekladačov dokážte, že nasledovné jazyky nie sú bezkontextové:
\begin{enumerate}[label=(\roman*)]
\item $ L_1 = \{ w \in \{a,b,c,d \}^* ~|~ \#_b(w)=\#_c(w)=\#_d(w) \} $
\item $ L_2 = \{ c^{2n}b^{n}(dc)^{24n} ~|~ n \in \N \} $
\end{enumerate}

Môžete predpokladať, že $\{ a^nb^nc^n ~|~ n \in \N \} \notin \Lcf$. O žiadnom inom jazyku nemôžete predpokladať, že nie je bezkontextový.

\item
Máme dané

\begin{align*}
L_1 &= \{ w \in \{a,b\}^* ~|~  \#_a(w) = \#_b(w) \} \\
L_2 &= \{ w \in \{a,b\}^* ~|~ \#_a(w) \equiv \#_b(w) \pmod{2} \}
\end{align*}

Zostrojte a-prekladač $M_1$ taký, že $M_1(L_1)=L_2$ alebo dokážte, že sa to nedá.\\
Zostrojte a-prekladač $M_2$ taký, že $M_2(L_2)=L_1$ alebo dokážte, že sa to nedá.


\end{enumerate}

\end{document}
