\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{9}{7.\,12.\,2009}

\noindent {\bf 1. [2 body]} Nechť ${\cal A} = (\{
q_0,q_1,q_2,q_3,q_4,q_5 \}, \{a,b\}, \{Z, A\}, \delta, q_0, Z,
\{q_5\})$ je zásobíhový automat, kde

\begin{tabbing}
$\delta(q_0,a,Z) = \{(q_1,AZ) \}$ \= \\
$\delta(q_0,a,A) = \{ (q_1,AA) \}$ \> \\
$\delta(q_1,a,A) = \{ (q_2,AA) \}$ \> \\
$\delta(q_2,a,A) = \{ (q_0,A), (q_3,A) \} $  \> \\
$\delta(q_3,b,A) = \{ (q_4,\varepsilon) \} $  \> \\
$\delta(q_3,b,Z) = \{ (q_5,\varepsilon)\}$ \> \\
$\delta(q_4,b,A) = \{ (q_3, A), (q_3, \varepsilon)\}$ \> \\
$\delta(q_4,b,Z) = \{ (q_5,\varepsilon)\}$ \> \\
\end{tabbing}

Popište jazyk~$L({\cal A})$, tedy jazyk akceptovaný automatem~${\cal
  A}$ koncovým stavem.


\newpage

\zadani{9}{7.\,12.\,2009}

\noindent
{\bf 2. [2 body]} Mějme bezkontextovou gramatiku $G =
(\{S,A,B\},\{a,b,c\},P,S)$, kde
\begin{tabbing}
$P = \{$ \= $S\ $ \= $\rightarrow aSa \mid AB \mid aa$, \\
\> $A$ \> $\rightarrow bAb \mid SS$, \\
\> $B$ \> $\rightarrow cBc \mid AA~\}$.
\end{tabbing}
Zkonstruujte ekvivalentní gramatiku v Greibachové normální formě.
Použijte algoritmus uvedený na přednášce. Popište svůj postup a uveďte
hlavní mezivýsledky.

\end{document}

