% Ondrej Jombik <nepto@pobox.sk>
% [6/3/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}	% dlhe 'l'
\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
\def\Dm{\v{D}}	% 'D' s makcenom
\title{Form{\ad}lne jazyky a automaty}
\author{Copyright \copyright{} 2001 Ondrej Jomb{\id}k} 

\begin{document}
\maketitle

\section{Zadanie}

\par
Pre dan{\yd} LBA A zostrojte LBA A' tak{\yd}, {\zm}e 
\begin{center}
$L(A')=\{w^R~|~w \in L(A)\}$.
\end{center}
Matematickou indukciou dok{\ad}{\zm}te spr{\ad}vnos{\tm} kon{\sm}trukcie.

\section{Rie{\sm}enie}

\par
Nech
\begin{center}
$A=(\Sigma, \Gamma, K, F, \delta, q_0)$.
\end{center}
Potom
\begin{center}
$A'=(\Sigma, \Gamma, K', F, \delta', q_0')$,
\end{center}
pri{\cm}om plat{\id}, {\zm}e
\\
\par
$\delta'$:$\left\{
\begin{array}{rclc}
\delta(q_0', a) & = & \{(q_0', a, 1)\}, a \in \Sigma & (1)\\
\delta(q_0', \$) & = & \{(q_0, \$, -1)\} & (2)\\\\
(q', a', p') \in \delta(q, a) & \Rightarrow & 
(q', a', -p) \in \delta'(q, a), a \in \Gamma - \{c, \$\} & (3)\\
(q', \$, p) \in \delta(q, \$) & \Rightarrow & 
(q', c, -p) \in \delta'(q, c) & \\
(q', c, p) \in \delta(q, c) & \Rightarrow & 
(q', \$, -p) \in \delta'(q, \$) & \\
\end{array}\right\}$
\\
\\
\par
Z{\ad}kladn{\ad} my{\sm}lienka spo{\cm}{\id}va v za{\cm}iato{\cm}nom presune
hlavy na koniec vstupnej p{\ad}sky. Nasledovn{\yd} postup bude pod{\lm}a
$\delta'$, teda pod{\lm}a p{\^o}vodnej $\delta$-funkcie, ale s posunom hlavy
opa{\cm}n{\yd}m smerom, ako bol smer p{\^o}vodn{\ed}ho automatu.
\\
\par
Je e{\sm}te nutn{\ed} o{\sm}etri{\tm} spr{\ad}vanie automatu na
za{\cm}iato{\cm}nom znaku $c$ a koncovom znaku $\$$. V t{\yd}chto pr{\id}padoch
sa bude nov{\yd} automat spr{\ad}va{\tm} akoby pre{\cm}{\id}tal $\$$ namiesto
$c$, resp. $c$ namiesto $\$$.

\section{D\^okaz}
\underline{$\{w^R~|~w \in L(A)\} \subseteq L(A')$:} 
\\
\par
Ak m{\ad}me nejak{\ed} slovo $w \in L(A)$ a k nemu prisl{\ud}chaj{\ud}ci
akcepta{\cm}n{\yd} v{\yd}po{\cm}et v automate $A$, potom automat $A'$ by mal
akceptova{\tm} slovo $w^R$.
\\
\par
A naozaj. Automat $A'$ skuto{\cm}ne akceptuje $w^R$. Akcepta{\cm}n{\yd}
v{\yd}po{\cm}et vych{\ad}dza z p\^ovodn{\ed}ho v{\yd}po{\cm}tu. Najsk\^or sa
mus{\id}me dosta{\tm} na koniec slova. Na to sa pou{\zm}ije $|w|-1$ kr{\ad}t
$(1)$ a hne{\dm} nato jeden kr{\ad}t $(2)$. 
\\
\par
{\Dm}alej pokra{\cm}ujeme pomocou $(3)$, {\cm}o vlastne zodpoved{\ad}
p\^ovodn{\ed}mu v{\yd}po{\cm}tu, ale s upraven{\yd}mi pravidlami.
\\
\par
Z kon{\sm}trukcie $\delta$-funkcie vypl{\yd}va, {\zm}e ide skuto{\cm}ne o
akcepta{\cm}n{\yd} v{\yd}po{\cm}et, preto{\zm}e automat, odvtedy ako zmenil
prv{\yd}kr{\ad}t stav na $q_0'$, sa spr{\ad}va ako p\^ovodn{\yd} automat
spracov{\ad}vaj{\ud}ci obr{\ad}ten{\ed} slovo.
\\
\\
\underline{$L(A') \subseteq \{w^R~|~w \in L(A)\}$:} 
\\
\par
Mus{\id}me uk{\ad}za{\tm}, {\zm}e automat $A'$ akceptuje len slov{\ad} z
mno{\zm}iny $\{w^R~|~w \in L(A)\}$.
\\
\par
D\^okaz vykon{\ad}me matematickou indukciou vzh{\lm}adom na d{\ld}{\zm}ku
krokov v{\yd}po{\cm}tu. Nech m{\ad} teda slovo $w$ d{\ld}{\zm}ku $n$.
Po{\cm}n{\ud}c d{\ld}{\zm}kou v{\yd}po{\cm}tu $n+1$ uk{\ad}{\zm}eme, {\zm}e
ku ka{\zm}dej konfigur{\ad}cii do ktorej sa po{\cm}as akcepta{\cm}n{\ed}ho
v{\yd}po{\cm}tu slova $w^R$ automat $A'$ dostane, existuje po{\cm}as
akcepta{\cm}n{\ed}ho v{\yd}po{\cm}tu slova $w$ nejak{\ad}
konfigur{\ad}cia automatu $A$.

\begin{enumerate}
\item[$1^\circ$] Po $n+1$ krokoch, ktor{\ed} samozrejme tvorilo $n$
pou{\zm}it{\id} pravidla $(1)$ nasledovan{\ed}ho hne{\dm} $(2)$, sa automat
$A'$ nach{\ad}dza v konfigur{\ad}cii $(q_0', cw^R\$, n)$, ktor{\ad}
zodpoved{\ad} konfigur{\ad}cii automatu A $(q_0', cw\$, 1)$, teda
konfigur{\ad}cii na za{\cm}iatku v{\yd}po{\cm}tu.

\item[$2^\circ$] Nech m{\ad} konfigur{\ad}cia automatu $A'$ po $n+k$ krokoch
st{\ad}le po{\zm}adovan{\yd} tvar. Uk{\ad}{\zm}eme, {\zm}e aj po $n+k+1$
krokoch bude ma{\tm} konfigur{\ad}cia automatu $A'$ po{\zm}adovan{\yd} tvar,
tzn. {\zm}e bez z{\ad}vislosti na tom, ak{\ed} pravidlo pou{\zm}ijeme,
ostane v{\yd}po{\cm}et st{\ad}le ekvivalentn{\yd} s akcepta{\cm}n{\yd}m
v{\yd}po{\cm}tom pre slovo $w$ v p\^ovodnom automate $A$.
\par
Nech sa teda automat $A'$ nach{\ad}dza v konfigur{\ad}cii $(q, cw^R\$, p)$,
ktor{\ad} je ekvivalentn{\ad} s konfigur{\ad}ciou $(q, cw\$, n-p+1)$ v
p\^ovodnom automate $A$. Ke{\dm}{\zm}e u{\zm} prebehlo viac ako $n+1$ krokov
v{\yd}po{\cm}tu, nem\^o{\zm}e automat pou{\zm}i{\tm} ani $(1)$, ani $(2)$,
preto{\zm}e sa u{\zm} ned{\ad} dosiahnu{\tm} stav $q_0'$.
\par
Preto mus{\id} pou{\zm}i{\tm} nejak{\ed} in{\ed} pravidlo okrem $(1)$ a $(2)$,
{\cm}i{\zm}e nie{\cm}o z $(3)$. Pravidl{\ad} $(3)$ v{\sm}ak ako vieme,
vznikli prepisom p\^ovodnej $\delta$-funkcie. Teda ku ka{\zm}d{\ed}mu z
t{\yd}chto pravidiel existuje pr{\ad}ve jedno ekvivalentn{\ed} pravidlo z
pravidiel, ktor{\ed} by mohol pou{\zm}i{\tm} p\^ovodn{\yd} automat $A$.
\par
Ke{\dm}{\zm}e mno{\zm}ina akcepta{\cm}n{\yd}ch stavov je u oboch automatov
rovnak{\ad}, v{\yd}po{\cm}ty sa dostan{\ud} do akcepta{\cm}n{\yd}ch stavov na
ekvivalentn{\yd} po{\cm}et krokov. Teda ak automat $A$ sa dostal do
akcepta{\cm}n{\ed}ho stavu na $m$ krokov, automat $A'$ sa dostane do
akcepta{\cm}n{\ed}ho stavu na $m+n+1$ krokov.
\end{enumerate}

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