\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\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{2}{10.\,10.\,2011}

\noindent 
{\bf 1. [2 body]} Mějme následující jazyk:
\[L = \{w \in \{k,o,s\}^*\mid w \text{ neobsahuje podslovo }
	kokos \text{ ani podslovo } koks\} 
\]
Sestrojte totální deterministický konečný automat
přijímající jazyk $L$.

\emph{Varianta za 1 bod:}
Pokud toto zadání nezvládnete, zkuste sestrojit automat pro jazyk
všech slov nad abecedou $\{k,o,s\}$ neobsahujících pouze podslovo $kokos$.
\newpage

\zadani{2}{10.\,10.\,2011}

\noindent
{\bf 2. [2 body]} Mějme následující gramatiku (nemusí být regulární)
  s vynechanou částí pravidel:\\
\[G = (\{S,A,B,C,D,E,F\}, \{0,1\}, P, S)\]
\[\begin{array}{crcl}
P = \{ & S & \rightarrow & 0 \mid 1 A, \\
       \ & A & \rightarrow & 0 B \mid 1 C, \\
       \ & B & \rightarrow & 0 D \mid 1 E, \\
       \ & C & \rightarrow & 0 F \mid 1 A, \\
       \ & D & \rightarrow & 0 B \mid 1 C, \\
       \ & E & \rightarrow & 0 D \mid 1 E, \\
       \ & F & \rightarrow & ???~~ \}\\
\end{array}\]
Doplňte do gramatiky pravidla pro neterminál $F$ tak, aby gramatika generovala
jazyk
\[ L = \{ w \in \{0,1\}^* 
	\mid w \text{ je binární zápis čísla dělitelného } 6\}.
\]
Své řešení zdůvodněte.

\emph{Nápověda:} Je třeba přidat tři pravidla.

\end{document}
