% Ondrej Jombik <nepto@pobox.sk>
% [20/2/2001] - vytvorenie dokumentu
% [21/2/2001] - drobne upravy

\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\Ud{\'U}	% dlhe 'U'
\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$=\{w~|~w \in \{a,b,c\}^* \textrm{ tak\'e, \v{z}e } \#_aw=\#_bw=\#_cw\}$
\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=$\{A, B, C, \sigma\}$, T=$\{a, b, c\}$,
P=$\{p_{10}, p_{20}, p_{21}, p_{22}, p_{23}, p_{24}, p_{25},
p_{30}, p_{31}, p_{32}\}$ pri{\cm}om plat{\id}, {\zm}e\\ 

$\begin{array}{rcrcl}
p_{10} & = & \sigma & \rightarrow & ABC\sigma~|~\epsilon\\
p_{20} & = & AB & \rightarrow & BA\\
p_{21} & = & BA & \rightarrow & AB\\
p_{22} & = & BC & \rightarrow & CB\\
p_{23} & = & CB & \rightarrow & BC\\
p_{24} & = & AC & \rightarrow & CA\\
p_{25} & = & CA & \rightarrow & AC\\
p_{30} & = & A & \rightarrow & a\\
p_{31} & = & B & \rightarrow & b\\
p_{32} & = & C & \rightarrow & c\\
\end{array}$

\section{D\^okaz}

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

\par
Uva{\zm}ujme ako vyzer{\ad} slovo vygenerovan{\ed} gramatikou G. Na
za{\cm}iatku m{\ad}me slovo $\sigma$, ktor{\ed} na{\sm}im podminekam evidentne
vyhovuje. Po aplikovan{\id} pravidla $p_{10}$ sa s{\id}ce zmen{\id}
po{\cm}et netermin{\ad}lov, ale podmienka ost{\ad}va aj na{\dm}alej splnen{\ad}.
Toto m\^o{\zm}eme zov{\sm}eobecni{\tm} na $n$ pou{\zm}it{\id} 
pravidla $p_{10}$.
\\
\par
Pravidl{\ad} $p_{20}, ..., p_{25}$ nemenia ani po{\cm}et netermin{\ad}lov, ani
po{\cm}et termin{\ad}lov, tak{\zm} po ich aplikovan{\id} ostane takisto
podmienka jazyka L splnen{\ad}.
\\
\par
A nakoniec pravidl{\ad} $p_{30}, p_{31}, p_{32}$, ktor{\ed} zamie{\nm}aj{\ud}
pr{\id}slu{\sm}n{\ed} netermin{\ad}ly za termin{\ad}ly.
\\
\par
V{\sm}eobecn{\yd} tvar odvodenia teda je

\begin{center}
$\sigma\Rightarrow^*_{p_{10}} (ABC)^n\epsilon
\Rightarrow_{p_{10}} (ABC)^n
\Rightarrow^*_{(p_{20}|p_{21}|p_{22}|p_{23}|p_{24}|p_{25})} X
\Rightarrow^*_{(p_{30}|p_{31}|p_{32})} x$,
\end{center}

kde $n \in \{0, 1, 2, ...\}$,  
$X$ je bu{\dm} $\epsilon$, 
alebo {\lm}ubovo{\lm}n{\ad} permut{\ad}cia slova $(ABC)^i$ a
$x$ je tiez bu{\dm} $\epsilon$, 
alebo {\lm}ubovo{\lm}n{\ad} permut{\ad}cia slova $(abc)^i$.
\\
\par
A t{\yd}m je inkl{\ud}zia L(G)$\subseteq$L dok{\ad}zan{\ad}.
\\
\\
L $\subseteq$ L(G):\\

\par
D\^okaz vykon{\ad}me matematickou indukciou vzh{\lm}adom na po{\cm}et
jedn{\ed}ho z termin{\ad}lov v slove $w$. Bez ujmy na v{\sm}eobecnosti
uva{\zm}ujme o termin{\ad}lovom p{\id}smene $a$.

\begin{enumerate}
\item[$1^\circ$] Nech $n=1$, {\cm}ize  $\#_aw=1$ a teda aj $\#_bw=\#_cw=1$.
Potom taktiez $|w|=3$. Teda odvodenie je 

\begin{center}
$\sigma\Rightarrow_{p_{10}} ABC\Rightarrow_{p_{20}} BAC\Rightarrow_{p_{22}} BCA
\Rightarrow_{p_{24}} CBA\Rightarrow_{p_{21}} CAB\Rightarrow_{p_{23}} ACB$,
\end{center}

pri{\cm}om v ka{\zm}dom tvare odvodenia (okrem prv{\ed}ho) sme mohli
aplikova{\tm} pravidl{\ad} $p_{30}, p_{31}, p_{32}$ a t{\yd}m dosta{\tm}
po{\zm}adovan{\yd} tvar obsahuj{\ud}ci len termin{\ad}lov{\ed} p{\id}smen{\ad}.

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

\begin{center}
$w=uvxy$, kde $u, v, x, y \in \{a, b, c\}^*$,
\end{center}

ktor{\ed} je generovan{\ed} gramatikou G, {\cm}i{\zm}e plat{\id}, {\zm}e 
$\#_aw=\#_bw=\#_cw$. Jeho tvar odvodenia je potom

\begin{center}
$\sigma\Rightarrow^*_{p_{10}} (ABC)^n
\Rightarrow^* UVXY \Rightarrow^*_{(p_{30}|p_{31}|p_{32})} uvxy = w$, 
\end{center}

kde U, V, X, Y obsahuj{\ud} netermin{\ad}ly A, B, C tak, aby po pou{\zm}it{\id}
pravidiel $p_{30}, p_{31}, p_{32}$ vzniklo slovo $vxyz$. Dok{\ad}{\zm}me teraz,
{\zm}e vieme vygenerova{\tm} aj slovo

\begin{center}
$w'=ut_1vt_2xt_3y$, kde $u, v, x, y \in \{a, b, c\}^*$, 
$t_1, t_2, t_3 \in \{a, b, c\}$
\end{center}

pre ktor{\ed} zarove{\nm} plat{\id}, {\zm}e slovo $t_1t_2t_3$ je
{\lm}ubovo{\lm}nou permut{\ad}ciou
slova $abc$. Bez ujmy na v{\sm}eobecnosti m\^ozeme predpoklada{\tm}, {\zm}e
$t_1t_2t_3=abc$, preto{\zm}e ostatn{\ed} pr{\id}pady pre in{\ed} mo{\zm}nosti
slova $t_1t_2t_3$ sa dokazuj{\ud} obdobne. Tak{\zm}e odvodenie slova $w'$ bude
na z{\ad}klade slova $w$, teda

\begin{center}
$\sigma\Rightarrow^*_{p_{10}} (ABC)^nABC
\Rightarrow^* UVXYABC \Rightarrow^* UAVBXCY 
\Rightarrow^*_{(p_{30}|p_{31}|p_{32})} uavbxcy = w'$.
\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}