\documentclass[12pt]{ib102}
\usepackage[czech]{babel}\usepackage{enumerate}

\setassignment{11}
\setexercise{2}
\setduedate{16}{12}{2013}
\setpoints{2}

%%% ZDE NAPISTE SVOJE UCO, JMENO A SKUPINU
\setstudent{James Bond}
\setgroup{MI6}
\setuco{007}


\begin{document}
\begin{zadani}
	\begin{enumerate}[(a)]
		\item Připomeňme definici třídy coNP: 
		$$ \mathrm{coNP} = \{ \mathrm{co-}L \mid L \in \mathrm{NP} \}.$$
		Dokažte, že platí inkluze $\mathrm{P} \subseteq \mathrm{NP} \cap \mathrm{coNP}$. Tedy ukažte, že každý jazyk $L \in \mathrm{P}$ splňuje $L \in \mathrm{NP}$ a zároveň $L \in \mathrm{coNP}$.
		\item \label{regularIsLinearTime} Neformálně zdůvodněte, proč každý regulární jazyk $R$ splňuje $R \in \mathrm{TIME}(n)$. Tedy vysvětlete, proč pro každý regulární jazyk existuje Turingův stroj, který ho rozhoduje, a navíc má lineární časovou složitost vzhledem k~délce vstupního slova.
	\end{enumerate}

	\bigskip
	\noindent
	\textbf{Bonus:\, [+1 bod]}\, Úlohu \eqref{regularIsLinearTime} dokažte formálně. Přesně popište převod konečného deterministického automatu na jazykově ekvivalentní Turingův stroj. Zdůvodněte, proč má Turingův stroj, který vznikne touto konstrukcí, lineární časovou složitost.
\end{zadani}

\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
