\documentclass[12pt]{article}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath, amssymb}
\usepackage[all]{xy}
\usepackage{xypic}\input xy \xyoption{all}


\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{\cA}{{\cal A}}

\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{8}{30.\,11.\,2009}
\noindent {\bf 1. [2 body]} Rozhodněte, zda je jazyk $$L = \{ ucu' \mid u,u'\in
\{a,b\}^*,~\#_a(u) = \#_b(u'),~\#_b(u) = \#_a(u')\}$$ bezkontextový. Pokud
jste rozhodli, že je bezkontextový, napište pro něj bezkontextovou
gramatiku. V opačném případě dokažte, že $L$ není bezkontextový.  

\newpage

\zadani{8}{30.\,11.\,2009}
\noindent {\bf 2. [2 body]} Mějme bezkontextovou gramatiku $G = ( \{ S,A,B,C,D,E
,F,G,H \}, \{ a,b,c \}, P, S)$, kde

\medskip\medskip
\setlength{\tabcolsep}{3pt}

\begin{tabular}{crcl}
$P = \{$ & $S$ & $\rightarrow$ & $aAb \mid BD $, \\
       \ & $A$ & $\rightarrow$ & $ACE \mid BcB \mid AF \mid bAa \mid H \mid a $,
 \\
       \ & $B$ & $\rightarrow$ & $D \mid bb \mid \eps $, \\
       \ & $C$ & $\rightarrow$ & $BDC \mid CcF \mid cc \mid \eps $, \\
       \ & $D$ & $\rightarrow$ & $SS \mid aFG \mid C $, \\
       \ & $E$ & $\rightarrow$ & $FE \mid EF $, \\
       \ & $F$ & $\rightarrow$ & $Eabc $, \\
       \ & $G$ & $\rightarrow$ & $GG \mid GE \mid abc $, \\
       \ & $H$ & $\rightarrow$ & $FF \mid A \ \}$.\\
\end{tabular}

\medskip\medskip\medskip
\noindent Zkonstruujte vlastní bezkontextovou gramatiku $G'$ takovou, že $L(G')=
L(G)$.

\end{document}

%%% Local Variables: 
%%% TeX-command-default: "LaTeX"
%%% End: 








