\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\usepackage{tikz}
\usetikzlibrary{calc}
\pagestyle{empty}

\topmargin -3mm
\headsep 0mm
\headheight 3mm
\textheight 235mm
\textwidth 165mm
\oddsidemargin 0mm
\evensidemargin 0mm
\footskip 10mm

\newcommand{\eps}{\varepsilon}
\newcommand{\coL}{co\mbox{$-$}L}
\newcommand{\move}{\rightarrow}
\renewcommand{\mod}{\ \mathrm{mod}\ }

\newcommand{\zadani}[2]{
{\large
\noindent {\bf IB102 -- úkol #1 \hfill Odevzdání: #2\\[-4mm]}
\noindent\hrule
\vspace{2mm}
\noindent Vypracoval(a):\hspace{7cm}UČO:\\
\noindent Skupina:
\vspace{2mm}
\hrule
\bigskip}
}


%%% ZDE NAPISTE SVOJE JMENO, UCO A SKUPINU
\newcommand{\reseni}[2]{
{\large
\noindent {\bf  IB102 -- úkol #1 -- řešení \hfill Odevzdání: #2\\[-4mm]}
\noindent\hrule
\vspace{2mm}
\noindent Vypracoval: James Bond \hspace{4.2cm}UČO: 007\ \ \\
\noindent Skupina: MI6
\vspace{2mm}
\hrule
\bigskip}
}


\begin{document}

%%% ZMENTE \zadani NA \reseni
\zadani{4}{24.\,10.\,2011}

\noindent 
{\bf 1. [2 body]} 
\begin{enumerate}
\item[a)] Uvažme abecedu $\Sigma = \{a\}$ a relaci $R_a$ nad $\Sigma^*$ definovanou takto:
\begin{align*}
u \, R_a \, v \iff |u| \mod 3 = 0 \wedge |v| \mod 3 = 0.
\end{align*}
\begin{itemize}
\item Rozhodněte, která slova z množiny $\{\epsilon,a,aa,aaa,aaaa\}$ jsou spolu v relaci a která nikoliv a výsledek znázorněte do obrázku níže, tj. spojte šipkou vedoucí z $u$ do $v$ všechna $u$ a  $v$ taková, že $u \, R_a \,  v$. Pokud $u \, R_a \,  v$ i $v \, R_a \,  u$, můžete použít "dvojšipku" -- jednu čáru se šipkami na obou koncích. Nezapomeňte udělat šipku z $u$ do $u$ v případě, že $u \, R_a \, u$.   
\item Je $R_a$ ekvivalence? Zdůvodněte.
\item Je $R_a$ pravá kongruence? Zdůvodněte.
\end{itemize}
\item[b)] Proveďte totéž pro relaci $R_b$ nad $\Sigma^*$ definovanou takto:
\begin{align*}
u \, R_b \, v \iff (|u| \mod 3 = 0 \iff |v| \mod 3 = 0).
\end{align*}
\end{enumerate}

\bigskip\bigskip

\begin{minipage}{0.6\linewidth}
a)

\tikzstyle{nod}=[circle,outer sep=0pt,inner sep=0pt]
\tikzstyle{popis}=[above=4pt]
\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
  \matrix[row sep=1.6cm,column sep=0.5cm] {
    & & \node[label=above: $\epsilon$] (a13) [nod] {}  circle (2pt) [fill] ; & &
    \\
    \node[label=left:$aaaa$] (a21) [nod] {}  circle (2pt) [fill]; & & & &
    \node[label=right:$a$] (a25) [nod] {}  circle (2pt) [fill]; 
    \\
    & \node[label=below:$aaa$] (a32) [nod] {}  circle (2pt) [fill]; & & 
    \node[label=below:$aa$] (a34) [nod] {}  circle (2pt) [fill]; & &
    \\
    };
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.4\linewidth}
b)

\tikzstyle{nod}=[circle,outer sep=0pt,inner sep=0pt]
\tikzstyle{popis}=[above=4pt]
\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
  \matrix[row sep=1.6cm,column sep=0.5cm] {
    & & \node[label=above: $\epsilon$] (b13) [nod] {}  circle (2pt) [fill] ; & &
    \\
    \node[label=left:$aaaa$] (b21) [nod] {}  circle (2pt) [fill]; & & & &
    \node[label=right:$a$] (b25) [nod] {}  circle (2pt) [fill]; 
    \\
    & \node[label=below:$aaa$] (b32) [nod] {}  circle (2pt) [fill]; & & 
    \node[label=below:$aa$] (b34) [nod] {}  circle (2pt) [fill]; & &
    \\
    };
\end{tikzpicture}
\end{minipage}

\bigskip
\bigskip
\noindent
{\bf Bonus: [+1 bod]} 

\begin{enumerate}
\item[c)] Proveďte totéž pro relaci $R_c$ nad $\Sigma^*$ definovanou takto:
\begin{align*}
u \, R_c \, v \iff (|u| \mod 3 = 0 \Rightarrow |v| \mod 3 = 0).
\end{align*}
\end{enumerate}
\newpage
c)

\tikzstyle{nod}=[circle,outer sep=0pt,inner sep=0pt]
\tikzstyle{popis}=[above=4pt]
\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
  \matrix[row sep=1.6cm,column sep=0.5cm] {
    & & \node[label=above: $\epsilon$] (c13) [nod] {}  circle (2pt) [fill] ; & &
    \\
    \node[label=left:$aaaa$] (c21) [nod] {}  circle (2pt) [fill]; & & & &
    \node[label=right:$a$] (c25) [nod] {}  circle (2pt) [fill]; 
    \\
    & \node[label=below:$aaa$] (c32) [nod] {}  circle (2pt) [fill]; & & 
    \node[label=below:$aa$] (c34) [nod] {}  circle (2pt) [fill]; & &
    \\
    };
\end{tikzpicture}

%%% SEM PISTE SVE RESENI

\newpage

%%% ZMENTE \zadani NA \reseni
\zadani{4}{24.\,10.\,2011}

\noindent
{\bf 2. [2 body]} Rozhodněte a zdůvodněte, zda platí: 
\begin{itemize}
\item Existuje regulární jazyk $L \subseteq \{a,b\}^*$ a pravá kongruence $\sim$ na $\{a,b\}^*$ taková, že $L$ je sjednocením některých tříd rozkladu $\{a,b\}^*$ podle $\sim$ a \textbf{index $\sim$ je dvojnásobkem indexu $\sim_L$}.
\item Existuje regulární jazyk $L \subseteq \{a,b\}^*$ a pravá kongruence $\sim$ na $\{a,b\}^*$ taková, že $L$ je sjednocením některých tříd rozkladu $\{a,b\}^*$ podle $\sim$ a \textbf{index $\sim_L$ je dvojnásobkem indexu $\sim$}.
\end{itemize}
 
\noindent
(\emph{Pozn.} Pokud bude Vaše odpověď "ano, platí", uveďte zcela konkrétní příklad takového jazyka $L$ a pravé kongruence $\sim$, a zdůvodněte. Pokud bude Vaše odpověď "ne, neplatí", pokuste argumentovat, proč to neplatí pro žádný jazyk $L$ a žádnou pravou kongruenci $\sim$).

\bigskip
\noindent
{\bf Bonus: [+1 bod]} 

\medskip

Jak by se změnily odpovědi, pokud bychom netrvali na regularitě jazyka $L$? Zdůvodněte.

%%% SEM PISTE SVE RESENI

\end{document}
