% (c) 2002 Ondrej Jombik <nepto@pobox.sk>
% 27/2/2002 - vytvorenie dokumentu
% 28/2/2002 - pisanie dokumentu

\documentclass[a4paper,12pt]{article}
%\usepackage{a4wide}
\usepackage [czech]{babel}

\def\dateczech{%
  \def\today{\number\day.~\ifcase\month\or
    janu\'ara\or febru\'ara\or marca\or apr\'{\i}la\or m\'aja\or
    j\'una\or j\'ula\or augusta\or septembra\or okt\'obra\or
    novembra\or decembra\fi
    \space \number\year}}

\title{Form\'{a}lne jazyky a automaty}
\author{Copyright \copyright{} 2002 Ondrej Jomb\'{\i}k}

\begin{document}
\maketitle

\section{Zadanie}

\par
Zostrojte kontextov\'{u} gramatiku, ktor\'{a} generuje jazyk $L$, kde
\begin{center}
$L~=~\{a^ib^jc^id^j ~|~ i,j>=0\}$
\end{center}

\section{Rie\v{s}enie}

\par
V triede kontextov\'{y}ch gramat\'{\i}k t\'{a}to \'{u}loha nem\'{a}
rie\v{s}enie, preto\v{z}e nevieme zostroji\q t pr\'{a}zdne slovo
$\epsilon$. Sk\'{u}sme v\v{s}ak n\'{a}js\q t rie\v{s}enie v
triede roz\v{s}\'{\i}ren\'{y}ch kontextov\'{y}ch gramat\'{\i}k.

\vskip5mm
\par
Pre roz\v{s}\'{\i}ren\'{e} kontextov\'{e} gramatiky platia rovnak\'{e}
pravidl\'{a} ako pre kontextov\'{e} gramatiky s t\'{y}m, \v{z}e
m\^{o}\v{z}e existova\q t jedno pravidlo, ktor\'{e} n\'{a}m prevedie
sigmu na epsilon, tj. $\sigma \rightarrow \epsilon$.

\vskip5mm
\par
Rie\v{s}en\'{\i}m je teda gramatika

\begin{center}
$G~=~(N, T, P, \sigma)$
\end{center}

\par
kde

\begin{center}
$N~=~\{\sigma, \sigma_1, \sigma_2, B, C\}$

\vskip5mm
\par
$T~=~\{a, b, c, d\}$
\end{center}

\par
Mno\v{z}ina pravidiel je definovan\'{a} takto:

\begin{center}
\vskip5mm
\par
$P~=~\left\{
\begin{array}{rclc}
\sigma & \rightarrow & \sigma_1\sigma_2~|~\sigma_1~|~\sigma_2~|~\epsilon
& (p_1)\\
\sigma_1 & \rightarrow & a\sigma_1C~|~aC & (p_{21})\\
\sigma_2 & \rightarrow & B\sigma_2d~|~Bd & (p_{22})\\
CB & \rightarrow & BC & (p_3)\\
aB & \rightarrow & ab & (p_{41})\\
bB & \rightarrow & bb & (p_{42})\\
Cd & \rightarrow & cd & (p_{43})\\
Cc & \rightarrow & cc & (p_{44})\\
\end{array}\right\}$

\end{center}

\section{Zd\^{o}vodnenie}

\par
Pravidl\'{a} $p_1$ sl\'{u}\v{z}ia na rozdelenie slova na dve \v{c}asti.
Z\'{a}rove\v{n} rie\v{s}ia \v{s}pecifick\'{y} pr\'{\i}pad, ke\v{d}
$i=j=0$.

\vskip5mm
\par
Po tom, ako sa m\'{a}me slovo rozdelen\'{e}, vytvor\'{\i}me v prvej \v{c}asti pomocou
pravidiel $p_{21}$ $i$ termin\'{a}lov $a$ a $i$ netermin\'{a}lov $C$.
Podobne v druhej \v{c}asti, kde pomocou pravidiel $p_{22}$ vytvor\'{\i}me
$j$ netermin\'{a}lov $B$ a $j$ termin\'{a}lov $d$.

\vskip5mm
\par
V tejto f\'{a}ze m\'{a}me slovo v tvare

\begin{center}
$a^iC^iB^jd^j$
\end{center}

\par
Pravidlo $p_3$ sl\'{u}\v{z}i na v\'{y}menu netermin\'{a}lov $B$ a $C$.
Pomocou neho bud\'{u} netermin\'{a}ly $B$ postupova\q t smerom v\q lavo
a netermin\'{a}ly $C$ smerom vpravo.

\vskip5mm
\par
Nakoniec, ke\v{d} netermin\'{a}ly $B$ resp. $C$ dorazia na koniec
termin\'{a}lov $a$ resp. za\v{c}iatok termin\'{a}lov $d$, zmenia sa
tieto netermin\'{a}ly na svoje pr\'{\i}slu\v{s}n\'{e} termin\'{a}ly pod\q
la pravidiel $p_{41}$ a $p_{43}$. V\v{d}aka tejto zmene, pri ktorej
vznikn\'{u} nov\'{e} termin\'{a}ly $b$ a $c$, sa postupne pomocou
pravidiel $p_{42}$ a $p_{44}$ zmenia aj zvy\v{s}n\'{e} netermin\'{a}ly,
a\v{z} nakoniec dostaneme slovo v po\v{z}adovanom tvare

\begin{center}
$a^ib^jc^id^j$
\end{center}

\section{Z\'{a}ver}

\par
\'{U}lohu sa mi podarilo \'{u}spe\v{s}ne vyrie\v{s}i\q t a
dok\'{a}za\q t.

\end{document}