\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\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}

\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}
}

\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}

\zadani{5}{25.\,10.\,2010}

\noindent 
{\bf 1. [2 body]} Najděte jazyky $L_1$, $L_2$, $L_3$ a $L_4$ takové, aby byly splněny
následující podmínky:
\begin{itemize}
\item[(a)] Jazyky $L_1$, $L_2$ jsou různé a platí $\mathord{\sim_{L_1}} = \mathord{\sim_{L_2}}$.
\item[(b)] Jazyky $L_3$, $L_4$ jsou různé, platí $\mathord{\sim_{L_3}} \ne \mathord{\sim_{L_4}}$ a
zároveň existuje relace $\sim$ splňující podmínky Nerodovy věty pro oba tyto jazyky.\\
(\emph{Tj.~$\sim$ musí být relace pravé kongruence s konečným indexem taková, že $L_3$ je sjednocením 
některých tříd rozkladu podle $\sim$ a zároveň $L_4$ je sjednocením některých tříd rozkladu
podle $\sim$.})
\end{itemize}
Své řešení zdůvodněte, tj.~zejména popište všechny zmíněné relace, např.~tak, 
že popíšete jejich třídy rozkladu.

\newpage

\zadani{5}{25.\,10.\,2010}

\noindent
{\bf 2. [2 body]} Mějme následující jazyk:
\[L = \{w \in \{0,1\}^* \mid w \text{ je binární zápis čísla $k$ takového, že }
k \bmod 3 = 1\}\]
přičemž za binární zápis čísla považujeme pouze takový zápis,
který neobsahuje zbytečné levostranné nuly, tj.\ $0110$ pro nás není binární
zápis čísla, zatímco $110$ je.

\begin{itemize}
\item[(a)] Určete index $\sim_L$ a popište třídy rozkladu podle $\sim_L$.
\item[(b)] Popište relaci pravé kongruence $\sim$ s konečným indexem takovou,
      že $\mathord{\sim} \ne \mathord{\sim_L}$ a přitom $L$ je sjednocením 
      některých tříd rozkladu podle $\sim$.
\end{itemize}

\end{document}
