\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{4}{18.\,10.\,2010}

\noindent 
{\bf 1. [2 body]}
Nechť $L = \{ w \in \{a,b\}^* \mid \#_a(w) \text{ je sudý} \Rightarrow
\#_a(w) < \#_b(w) \}$. Rozhodněte, zda je jazyk $L$ regulární
a své tvrzení dokažte.\\
\emph{(K důkazu regularity jazyka stačí napsat příslušnou gramatiku nebo
automat.)}

\newpage

\zadani{4}{18.\,10.\,2010}

\noindent
{\bf 2. [2 body]}
Mějme gramatiku $G = (\{S,X,Y\}, \{a,b,c\}, P, S)$, kde
\[\begin{array}{crcl}
P = \{ & S & \rightarrow & XY, \\
       \ & Y & \rightarrow & aYa \mid bYb \mid c, \\
       \ & Xab & \rightarrow & baX, \\
       \ & Xc & \rightarrow & \varepsilon~~ \}\\
\end{array}\]
Popiše jazyk generovaný gramatikou $G$ a určete, zda je tento jazyk regulární.
Své tvrzení dokažte.

\end{document}
