\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath, amssymb}

\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}{20.\,10.\,2008}

\noindent
{\bf 1. [2 body]} Nechť $L$ je jazyk nad abecedou $\Sigma$ a $w \in \Sigma^*$.
Definujme následující operaci:
$$w/L = \{u\ |\ wu \in L\}$$
Například pro $L = \{ab, aba, bba\}$ platí $ab/L = \{\eps, a\}$.

Bez využití převodu na DFA uveďte obecný postup, kterým lze pro libovolný
nedeterministický konečný automat $\mathcal{M}$ bez $\eps$-kroků a slovo $w$
sestrojit automat $\mathcal{M'}$ (bez $\eps$-kroků), pro který platí
$L(\mathcal{M'}) = w/L(\mathcal{M})$. Tím dokážeme, že je třída regulárních
jazyků uzavřena na operaci $w/L$ pro každé $w$. Zdůvodněte správnost své
konstrukce.

\newpage

\zadani{5}{20.\,10.\,2008}

\noindent
{\bf 2. [2 body]} K zadanému nedeterministickému konečnému automatu
zkonstruujte ekvivalentní minimální konečný automat v kanonickém
tvaru. Konstrukci zde uveďte.

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


\end{document}


%%% Local Variables:
%%% TeX-command-default: "CsLaTeX"
%%% End:
