\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{5}{2.\,11.\,2009}
\noindent {\bf 1. [2 body]} K zadanému konečnému automatu zkonstruujte
ekvivalentní minimální konečný automat v kanonickém tvaru. Konstrukci zde
uveďte.

\noindent
\begin{tabular}[t]{|r|c|c|}
    \hline
    & $a$ & $b$ \\ \hline \hline
    $\rightarrow 1$ & $\emptyset$ & \{2,3\} \\ \hline
    2 & \{1,6\} & \{7\} \\ \hline 
    3 & $\emptyset$ & \{4,5,7\} \\ \hline 
    $\leftarrow$ 4 & \{6\} & \{2,8\} \\ \hline
    5 & \{1\} & $\emptyset$ \\ \hline
    6 & \{6\} & $\emptyset$ \\ \hline
    7 & $\emptyset$ & \{8\} \\ \hline
    $\leftarrow$ 8 & \{1\} & \{4,5\} \\ \hline    
\end{tabular}  

\newpage

\zadani{5}{2.\,11.\,2009}

\noindent {\bf 2. [2 body]} Nechť $\Sigma = \{a, b, c\}$ je pevná abeceda a
nechť $L$ je jazyk nad abecedou $\Sigma$. Definujme následující operaci:
$$\textsf{noaces}(L) = \{w\ |\ w \in L \wedge w\ \textnormal{neobsahuje
  podslovo}\ aa\}$$ Například pro $L = \{aba, aaa, bbaa, bbb\}$ platí
$\textsf{noaces}(L) = \{aba, bbb\}$.

Uveďte obecný postup, kterým lze pro libovolný deterministický konečný
automat $\mathcal{M}$ nad abecedou $\Sigma$ sestrojit deterministický
konečný automat $\mathcal{M'}$, pro který platí $L(\mathcal{M'}) =
\textsf{noaces}(L(\mathcal{M}))$. Zdůvodněte správnost své konstrukce.

\end{document}








