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


\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{\cA}{{\cal A}}

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


\noindent {\bf 1.} Je zadán konečný automat:


\vspace{-0.5em}

\[
  \SelectTips{cm}{10}
  \xymatrix@!=.5cm{
   && *+<5mm>[o][F-]{1} \ar[dr]^b & \\
   & *+<5mm>[o][F-]{2} \ar[ur]^a \ar@/^0.5pc/[rr]^b && *+<5mm>[o][F-]{3} \ar@/^0.5pc/[ll]^\varepsilon \ar[dd]_b \ar[ddll]_(0.7)\varepsilon&& \\
   \\
\ar[r]_{} & *+<5mm>[o][F-]{4} \ar[uu]^a \ar@/^0.5pc/[rr]^\varepsilon   && *+<5mm>[o][F=]{5} \ar@/^0.5pc/[ll]^a  \ar[uull]^(0.7)a
}
\]


\begin{itemize}
 \item a) {\bf [2 body]} zkonstruujte k němu ekvivalentní NFA bez $\eps$-kroků a napište i množiny $D_\varepsilon$ pro všechny stavy.

(Pokud nepoužijete standardní algoritmus, dokažte ekvivalenci původního automatu se zkonstruovaným NFA bez $\eps$-kroků).

\item b) {\bf [0 bodů]} nakreslete tento domeček jedním tahem (respektujte orientaci šipek, začít můžete v libovolném stavu)
\end{itemize}

\newpage

\zadani{6}{29.\,10.\,2008}

\noindent {\bf 2. [2 body]} Mějme tři regulární výrazy $r_1, r_2, r_3$ nad abecedou $\Sigma$. Je rozhodnutelné, zda konečný automat ekvivalentní výrazu $r_3$ akceptuje právě ta slova, které akceptuje automat
ekvivalentní $r_1$, kromě slov akceptovaných automatem ekvivalentním $r_2$? Pokud ano,
popište algoritmus na řešení problému (použijete-li algoritmy ze skript, nemusíte je podrobně popisovat).
Pokud ne, své tvrzení dokažte.

\end{document}


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

