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

\noindent 
{\bf 1. [2 body]}
Mějme gramatiku $G = (\{S,X,Y,Z\}, \{a,b,c\}, P, S)$, kde
\[\begin{array}{crcl}
P = 
\{& S & \rightarrow &  XZX , \\
\ & X & \rightarrow &  Xbc \mid  Ybc, \\
\ & Y & \rightarrow &  aa  \mid  Saa, \\
\ & Z & \rightarrow &  ZZb \mid  c ~~\}.\\
\end{array}\]
Ke gramatice $G$ sestrojte (použitím algoritmů z přednášky) ekvivalentní
gramatiku v Greibachové normální formě.

\newpage

\zadani{10}{6.\,12.\,2010}

\noindent
{\bf 2. [3 body]}
O následujících jazycích rozhodněte, zda jsou bezkontextové,
a své rozhodnutí dokažte. (V případě, že jazyk je bezkontextový,
nám bude jako důkaz stačit napsání příslušné bezkontextové gramatiky
nebo zásobníkového automatu.)
\begin{itemize}
\item[(a)] $L_1 = \{ w \mid w \in \{a,b\}^+, \#_a(w) = \#_b(w) \}^2$
\item[(b)] $L_2 = \{ w^2 \mid w \in \{a,b\}^+, \#_a(w) = \#_b(w) \}$
\end{itemize}
\end{document}
