\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{9}{29.\,11.\,2010}

\noindent 
{\bf 1. [2 body]}
Mějme následující jazyk:
\[L = \{ w \in \{a,b\}^* \mid w = w^R \} \cup 
\{ w \in \{a,b\}^* \mid \#_a(w) \bmod 2 = \#_b(w) \bmod 2\}\]
Sestrojte \emph{jednoznačnou} bezkontextovou gramatiku generující
jazyk $L$. Stručně vysvětlete, proč je Vaše gramatika jednoznačná.
\newpage

\zadani{9}{29.\,11.\,2010}

\noindent
{\bf 2. [3 body]}
Mějme gramatiku $G = (\{S,A,B,C,D,E,F\}, \{a,b,c\}, P, S)$, kde
\[\begin{array}{crcl}
P = 
\{& S & \rightarrow &  AB \mid  cC, \\
\ & A & \rightarrow & \varepsilon \mid  aA \mid SEb, \\
\ & B & \rightarrow & \varepsilon \mid  bB \mid AEc, \\
\ & C & \rightarrow &   D \mid AcB, \\
\ & D & \rightarrow &  Bb \mid Abc \mid   C, \\
\ & E & \rightarrow & abE \mid  Ec \mid  EF, \\
\ & F & \rightarrow &  Ea \mid  ba~~\}.\\
\end{array}\]
Ke gramatice $G$ sestrojte (použitím algoritmů z přednášky) ekvivalentní
gramatiku v Chomského normální formě.

\emph{Poznámka}: Gramatika v CNF musí být vždy redukovaná. 
\end{document}
