% Ondrej Jombik <nepto@pobox.sk>
% [22/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

\title{Form{\ad}lne jazyky a automaty}
\author{Copyright \copyright{} 2001 Ondrej Jomb{\id}k} 

\begin{document}
\maketitle

\section{Zadanie}

\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} L=L(G).

\section{Rie{\sm}enie}

\par
Uva{\zm}ujme kontextov{\ud} gramatiku G pre dan{\yd} jazyk, tak{\ud} {\zm}e
\begin{center}
G=(N, T, P, $\sigma$),
\end{center}
kde N=$\{X_1, X_2, T_1, T_2, A, B, \sigma\}$, T=$\{a, b\}$,
P=$\{p_{10}, p_{20}, p_{21}, p_{30}, p_{31}, p_{32}, p_{33},
p_{40}, p_{41}, p_{42}, p_{43}, p_{50}, p_{51}\}$
pri{\cm}om plat{\id}, {\zm}e\\ 

$\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}$

\section{D\^okaz}

L(G) $\subseteq$ L:\\

\par
Chceme dok{\ad}zat, {\zm}e v{\sm}etky slov{\ad} z{\id}skan{\ed} gramatikou G
patria do jazyka L. Uva{\zm}ujme ako vyzer{\ad} slovo vygenerovan{\ed}
gramatikou G a sk{\ud}majme pr{\id}slu{\sm}n{\ed} pravidl{\ad}.
\\
\par
Na za{\cm}iatku m{\ad}me slovo $\sigma$ a po aplikovan{\id} pravidiel $p_{10},
p_{20}, p_{21}$ dost{\ad}vame slovo v tvare $wxT_i$, kde $i=\{1, 2\}$ a 
podslovo $x$ po vypusten{\id} netermin{\ad}lov $A, B$ je vlastne $w^R$.
Ak teda ignorujeme netermin{\ad}lov{\ed} pismen{\ad} $A$ a $B$, m{\ad}me
slovo v tvare $ww^RT_i$ $(i=\{1, 2\})$.
\\
\par
Pravidl{\ad} $p_{30}, p_{31}, p_{32}, p_{33}$ maj{\ud} za {\ud}lohu
pres{\ud}va{\tm} netermin{\ad}ly $A$ a $B$ na koniec slova. Toto sa
vyu{\zm}{\id}va v spolupr{\ad}ci s {\dm}al{\sm}{\id}mi pravidlami $p_i$, kde
$i>=40$.
\\
\par
{\Dm}alej pravidl{\ad} $p_{40}, p_{41}, p_{42}, p_{43}$ transformuj{\ud}
najkrajnej{\sm}{\id} netermin{\ad}l $A$, resp. $B$ na termin{\ad}l
$a$, resp. $b$, pri{\cm}om sa na{\dm}alej vyu{\zm}{\id}vaj{\ud}
predch{\ad}dzaj{\ud}ce pravidl{\ad} na pos{\ud}vanie netermin{\ad}lov
$A$ a $B$ smerom na koniec slova.
\\
\par
Ako {\ud}plne na z{\ad}ver sa pou{\zm}ij{\ud} pravidl{\ad} $p_{50}, p_{51}$ na
fin{\ad}lnu konverziu koncov{\ed}ho netermin{\ad}lu $T_1$, resp. $T_2$ na
termin{\ad}l $a$, resp. $b$, po {\cm}om kone{\cm}ne dost{\ad}vame slovo
tvaru $ww^Rw$.
\\
\par
A t{\yd}m je inkl{\ud}zia L(G)$\subseteq$L dok{\ad}zan{\ad}.
\\
\\
L $\subseteq$ L(G):\\

\par
Chceme dok{\ad}zat, {\zm}e v{\sm}etky slov{\ad} z jazyka L sa daj{\ud}
z{\id}ska{\tm} gramatikou G. D\^okaz vykon{\ad}me matematickou indukciou
vzh{\lm}adom na d{\ld}{\zm}ku slova $u$, kde $|u|=n$.
\\
\par
Predpoklad{\ad}me, {\zm}e ak $u \in L$ vieme generova{\tm} gramatikou G, tak 
vieme generova{\tm} aj slovo $u' \in L$ ak plat{\id} $|u'|=|u|+3$.
\\
\begin{enumerate}
\item[$1^\circ$] Nech $n=3$. Odvodenie slova $u$ potom bude

\begin{center}
$\sigma\Rightarrow_{p_{10}} X_1T_1\Rightarrow_{p_{20}} aaa = u$
\end{center}

resp.

\begin{center}
$\sigma\Rightarrow_{p_{10}} X_2T_2\Rightarrow_{p_{21}} bbb = u$
\end{center}

\item[$2^\circ$] Mus{\id}me dok{\ad}za{\tm}, {\zm}e ak tvrdenie plat{\id} pre
$n$, tak plat{\id} aj pre $n+3$. Majme teda slovo

\begin{center}
$u=ww^Rw$, kde $w \in \{a, b\}^+$,
\end{center}

ktor{\ed}ho tvar odvodenia je 

\begin{center}
$\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$
\end{center}

kde $i \in \{1, 2\}$, $Z \in \{A, B, a, b\}$, pri{\cm}om plat{\id}
$\#_av=\#_aZ=\#_AZ$, $\#_bv=\#_bZ=\#_BZ$. Teda $|Z|=2|v|$. {\Dm}alej plat{\id},
{\zm}e $V$ je rovnak{\ed} slovo ako $v$, akur{\ad}t, {\zm}e na
pr{\id}slu{\sm}n{\yd}ch miestach obsahuje namiesto
termin{\ad}lov netermin{\ad}ly, tj. namiesto $a$ obsahuje $A$
a namiesto $b$ obsahuje $B$. 

Dok{\ad}{\zm}me teraz, {\zm}e vieme vygenerova{\tm} aj slovo

\begin{center}
$u'=wxxw^Rwx$, kde $w \in \{a, b\}^+$ a $x \in \{a, b\}$.
\end{center}

Jeho tvar odvodenia teda bude

\begin{center}
$\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'$.
\end{center}

\end{enumerate}

\par
Teda vieme gramtikou G generova{\tm} ka{\zm}d{\ed} slovo z jazyka L,
{\cm}{\id}m sme inkl{\ud}ziu L$\subseteq$L(G) dok{\ad}zali.
\\
\\
Ke{\dm}{\zm}e L(G)$\subseteq$L a z{\ad}rove{\nm} L$\subseteq$L(G), tak potom
L(G)=L.

\section{Z{\ad}ver}

\par
{\Ud}lohu sa mi podarilo {\ud}spe{\sm}ne vyrie{\sm}i{\tm} a dok{\ad}za{\tm}.

\end{document}