% Ondrej Jombik <nepto@pobox.sk>
% [26/2/2001] - vytvorenie dokumentu

\documentclass[a4paper]{article}
\usepackage{a4wide}

\def\tm{t\kern-0.035cm\char39\kern-0.03cm} % 't' s makcenom
\def\lm{l\kern-0.035cm\char39\kern-0.03cm} % 'l' s makcenom
\def\dm{d\kern-0.035cm\char39\kern-0.03cm} % 'd' s makcenom
\def\id{\'{\i}} % dlhe 'i'
\def\ud{\'u}	% dlhe 'u'
\def\ad{\'a}	% dlhe 'a'
\def\ed{\'e}	% dlhe 'e'
\def\yd{\'y}	% dlhe 'y'
\def\ld{\'l}	% 'l' s dlznom
\def\Ud{\'U}	% dlhe 'U'
\def\Dm{\v{D}}	% 'D' s makcenom
\def\zm{\v{z}}	% 'z' s makcenom
\def\cm{\v{c}}	% 'c' s makcenom
\def\sm{\v{s}}	% 's' s makcenom
\def\nm{\v{n}}	% 'n' s makcenom

\font\brm = cmr10 scaled \magstep 1
\font\bbrm = cmr10 scaled \magstep 2
\font\bbbrm = cmr10 scaled \magstep 3
\font\bbbbrm = cmr10 scaled \magstep 4
\font\bbbbbrm = cmr10 scaled \magstep 5 

\begin{document}
\hsize = 4 in
\parindent = 0 pt
\leftskip = 1 in

% PAGE 1


\begin{center}
\brm 
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
Form{\ad}lne jazyky a automaty\\
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
{\Ud}loha 4\\
\smallskip
Sada 1\\
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\rm
Ondrej Jomb{\id}k\\
2i2
\end{center}

%\eject
% PAGE 2

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\section{Zadanie}

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\par
Zostrojte kontextov{\ud} gramatiku G pre jazyk 
\begin{center}
L=$\{ww^Rw~|~w \in \{a, b\}^+\}$
\end{center}
a dok{\ad}{\zm}te spr{\ad}vnos{\tm} kon{\sm}trukcie,
teda {\zm}e plat{\id}
\begin{center}
L = L(G).
\end{center}

\eject
% PAGE 3

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\section{Defin{\id}cie}

\bigskip
\bigskip
\bigskip
\par
\underline{Defin{\id}cia:} Kontextov{\ad} gramatika je tak{\ad} fr{\ad}zov{\ad}
gramatika, v ktorej pre ka{\zm}d{\ed} pravidlo $u \Rightarrow v$ plat{\id}
$|u| \leq |v|$.

\bigskip
\bigskip
\bigskip

\par
\underline{Defin{\id}cia:} Fr{\ad}zov{\ad} gramatika je {\sm}tvorica
\begin{center}
G=(N, T, P, $\sigma$),
\end{center}
kde N a T s{\ud} abecedy netermin{\ad}lnych a termin{\ad}lnych symbolov
(N $\cap$ T = $\not 0$),
$\sigma \in$ N je po{\cm}iato{\cm}n{\yd} netermin{\ad}l a
{P $\subseteq$ (N $\cup$ T )$^*$N(N $\cup$ T)$^*$ $\times$
(N $\cup$ T)$^*$} je kone{\cm}n{\ad} mno{\zm}ina pravidiel.

%\eject
% PAGE 4

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip

\section{{\Ud}vahy}
\par
1. $ww^R$ vieme vygenerova{\tm} jednoducho\\
2. pre $ww^Rw$ ozna{\cm}{\id}me koniec slova\\
3. vytvor{\id}me netermin{\ad}ly\\
4. generujeme {\sm}peci{\ad}lne $ww^R$\\
5. posun netermin{\ad}lov na koniec\\
6. konverzia na termin{\ad}ly\\
7. z{\ad}mena koncov{\ed}ho znaku\\
8. $ww^Rw$

\eject
% PAGE 5

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\section{Rie{\sm}enie}

\par
\underline{G=(N, T, P, $\sigma$)}
\\\\
N=$\{X_1, X_2, T_1, T_2, A, B, \sigma\}$\\
T=$\{a, b\}$\\

P=$\left\{
\begin{array}{rcrcl}
p_{10} & = & \sigma & \rightarrow & X_1T_1~|~X_2T_2\\\\
p_{20} & = & X_1 & \rightarrow & aa~|~aX_1Aa~|~bX_1Bb\\
p_{21} & = & X_2 & \rightarrow & bb~|~aX_2Aa~|~bX_2Bb\\\\
p_{30} & = & Aa & \rightarrow & aA\\
p_{31} & = & Ab & \rightarrow & bA\\
p_{32} & = & Ba & \rightarrow & aB\\
p_{33} & = & Bb & \rightarrow & bB\\\\
p_{40} & = & AT_1 & \rightarrow & aT_1\\
p_{41} & = & AT_2 & \rightarrow & aT_2\\
p_{42} & = & BT_1 & \rightarrow & bT_1\\
p_{43} & = & BT_2 & \rightarrow & bT_2\\\\
p_{50} & = & T_1 & \rightarrow & a\\
p_{51} & = & T_2 & \rightarrow & b\\
\end{array}\right\}$

%\eject
% PAGE 6

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\section{D\^okaz (1.{\cm}as{\tm})}

\par
L(G) $\subseteq$ L: odvodzovanim pod{\lm}a P
\\
\par
1. $p_{10}, p_{11}$: po{\cm}iato{\cm}n{\yd} krok, zap{\id}{\sm}eme $T_i$\\
2. $p_{20}, p_{21}$: z{\ad}pis 2 termin{\ad}lov a 1 netermin{\ad}lu\\
3. $p_{30}, ..., p_{33}$: presun netermin{\ad}lov na koniec slova\\
4. $p_{40}, ..., p_{43}$:
transformacia krajn{\yd}ch netermin{\ad}lov na termin{\ad}ly;
mo{\zm}nos{\tm} n{\ad}vratu na (3)\\
5. $p_{50}, p_{51}$: fin{\ad}lna konverzia\\
6. vysledn{\ed} slovo v tvare $ww^Rw$

\eject
% PAGE 7

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\section{D\^okaz (2.{\cm}as{\tm})}

\par
L $\subseteq$ L(G): MI vzh{\lm}adom na d{\ld}{\zm}ku slova
\\
\par
{\bf $1^\circ$}
$\sigma\Rightarrow_{(p_{10}|p_{11})} X_1T_1
\Rightarrow_{(p_{20}|p_{21})} xxx = u$ 
\\
\\
{\bf $2^\circ$} \underline{ $u=ww^Rw$ }
\\
$\sigma\Rightarrow_{p_{10}} X_iT_i
\Rightarrow^{n-1}_{(p_{20}|p_{21})} vX_iZT_i$\\
$\Rightarrow^*_{(p_{30}|p_{31}|p_{32}|p_{33})} vX_iv^RV^RT_i$ \\
$\Rightarrow^{n-1}_{(p_{40}|p_{41}|p_{42}|p_{43})} vX_iv^RvT_i$\\
$\Rightarrow^*_{(p_{20}|p_{21}|p_{50}|p_{51})} ww^Rw = u$
\\
\\
\underline{ $u'=wxxw^Rwx$ }
\\
$\sigma\Rightarrow_{p_{10}} X_iT_i
\Rightarrow^{n-1}_{(p_{20}|p_{21})} vX_iZT_i$\\
$\Rightarrow_{(p_{20}|p_{21})} vxX_iXxZT_i$\\
$\Rightarrow^*_{(p_{30}|p_{31}|p_{32}|p_{33})} vxX_ixv^RXV^RT_i$\\
$\Rightarrow^{n-1}_{(p_{40}|p_{41}|p_{42}|p_{43})} vxX_ixv^RvxT_i$\\
$\Rightarrow^*_{(p_{20}|p_{21}|p_{50}|p_{51})} wxxw^Rwx = u'$



\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\section{Z{\ad}ver}
\bigskip
\bigskip
\par
L(G)$\subseteq$L $\wedge$ L$\subseteq$L(G) $\Rightarrow$ L(G)=L
\bigskip
\bigskip
\par
{\Ud}lohu sa mi podarilo {\ud}spe{\sm}ne vyrie{\sm}i{\tm} a dok{\ad}za{\tm}.

\end{document}
