\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage[all]{xy}

\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{\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{4}{26.\,10.\,2009}
\noindent {\bf 1. [2 body]} Nechť $\Sigma=\{a,b\}$ je abeceda. Rozhodněte,
zda jsou relace $\sim_1,\sim_2$ na $\Sigma^*$ pravé kongruence. Své tvrzení dokažte. 
\[
  \begin{array}{rcl}
  u \sim_1 v & \Longleftrightarrow & u=v ~~\textrm{nebo}~~ (|u|\cdot|v|)\bmod 2=0 \\[1ex]
  u \sim_2 v & \Longleftrightarrow & (\#_b(u)+\#_b(v))\bmod 2=0
  \end{array}
\]

\newpage

\zadani{4}{26.\,10.\,2009}
\noindent {\bf 2. [2 body]} Nechť $\Sigma=\{a,b\}$ je abeceda
a $$L=\{w\in\{a,b\}^*\mid w\textrm{~začíná písmenem $b$ a $\#_a(w)$ není dělitelný
  třemi}\}$$ je jazyk nad touto abecedou.
\begin{itemize}
\item Popište třídy rozkladu $\Sigma^*/\!\!\sim_L$ a určete index $\sim_L$.
\item Najděte relaci $\sim$ na $\Sigma^*$ takovou, že $\sim\,\neq\,\sim_L$,
  $\sim$ je pravou kongruencí s konečným indexem a $L$ je sjednocením
  některých tříd $\Sigma^*/\!\!\sim$. 
\end{itemize}

\end{document}
