% (c) 2002 Ondrej Jombik <nepto AT pobox.sk>
% 27/2/2002 - vytvorenie dokumentu
% 15/5/2002 - pisanie
%
% TODO: opa:tovnom

\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}
\newcommand{\cent}{\textrm{c\kern-0.3em\small$|$}}
\newcommand{\bicik}{\upharpoonright}
\maketitle

\section{Zadanie}

\par
Zostrojte LBA, ktor\'{y} bude akceptova\q t jazyk
\begin{center}
L$~=~\{a^{2^n} ~|~ n\ge0\}$
\end{center}

\section{Rie\v{s}enie}

\par
Rie\v{s}en\'{\i}m \'{u}lohy je nasledovn\'{y} automat

\par
\begin{center}
$A = (K, \Sigma, \Gamma, \delta, q_{begin}, F)$
\end{center}
\par
kde
\\
\par
$\begin{array}{rclc}
K & = & \{q_{begin}, q_{null}, q_{null\_back},q_{start},\\
& & q_{mark}, q_{forward_a}, q_{forward_b}, q_{determine},\\
& & q_{check_1}, q_{check_2}, q_{rewind_1}, q_{rewind_2},\\
& & q_{reset_1}, q_{reset_2}, q_{end}\},\\
F & = & \{q_{end}\},\\
\Sigma & = & \{a\},\\
\Gamma & = & \{a, a', b, B\}
\end{array}$.
\\
\par
Prechodov\'{a} funkcia $\delta$ vyzer\'{a} takto:

\par
\begin{center}
$\begin{array}{rclcl}
	(q_{begin}, a) & = & \{(q_{null}, B, 1)\} & (01) &\\
	(q_{null}, a) & = & \{(q_{null}, B, 1)\} & (02) &\\
	(q_{null}, \$) & = & \{(q_{null\_back}, \$, -1)\} & (03) &\\
	(q_{null\_back}, B) & = & \{(q_{null\_back}, B, -1)\} & (04) &\\
	(q_{null\_back}, \cent) & = & \{(q_{start}, \cent, 1)\} & (05) &\\
\\
	(q_{start}, B) & = & \{(q_{determine}, a', 0)\} & (11) &\\
	(q_{mark}, a) & = & \{(q_{forward_a}, a', 1)\} & (12) &\\
	(q_{forward_a}, a) & = & \{(q_{forward_a}, a, 1)\} & (13) &\\
	(q_{forward_a}, b) & = & \{(q_{forward_b}, b, 1)\} & (14) &\\
	(q_{forward_a}, \$) & = & \{(q_{determine}, \$, 0)\} & (15) &\\
	(q_{forward_a}, B) & = & \{(q_{determine}, b, 1)\} & (16) &\\
	(q_{forward_b}, b) & = & \{(q_{forward_b}, b, 1)\} & (17) &\\
	(q_{forward_b}, B) & = & \{(q_{determine}, b, 1)\} & (18) &\\
\\
	(q_{determine}, \$) & = & \{(q_{check_1}, \$, -1)\} & (21) &\\
	(q_{determine}, B) & = & \{(q_{rewind_1}, B, -1)\} & (22) &\\
	(q_{check_1}, b) & = & \{(q_{check_1}, b, -1)\} & (23) &\\
	(q_{check_1}, a') & = & \{(q_{check_2}, a', -1)\} & (24) &\\
	(q_{check_2}, a') & = & \{(q_{check_2}, a', -1)\} & (25) &\\
	(q_{check_2}, \cent) & = & \{(q_{end}, \cent, 0)\} & (26) &\\
\\
	(q_{rewind_1}, b) & = & \{(q_{rewind_1}, b, -1)\} & (31) &\\
	(q_{rewind_1}, a) & = & \{(q_{rewind_2}, a, -1)\} & (32) &\\
	(q_{rewind_1}, a') & = & \{(q_{reset_1}, a', 1)\} & (33) &\\
	(q_{rewind_2}, a) & = & \{(q_{rewind_2}, a, -1)\} & (34) &\\
	(q_{rewind_2}, a') & = & \{(q_{mark}, a', 1)\} & (35) &\\
\\
	(q_{reset_1}, b) & = & \{(q_{reset_1}, a', 1)\} & (41) &\\
	(q_{reset_1}, B) & = & \{(q_{reset_2}, B, -1)\} & (42) &\\
	(q_{reset_2}, a') & = & \{(q_{reset_2}, a, -1)\} & (43) &\\
	(q_{reset_2}, \cent) & = & \{(q_{mark}, \cent, 1)\} & (44) &\\
\end{array}$
\end{center}

\section{Popis}
\par

Va\v{c}\v{s}\'{\i} po\v{c}et stavov a pravidiel prechodovej funkcie je z
d\^{o}vodu zabezpe\v{c}enia automatu proti ne\v{z}iad\'{u}cemu
spr\'{a}vaniu. Ne\v{z}iad\'{u}cim spr\'{a}van\'{\i}m sa mysl\'{\i}
neakceptovanie niektor\'{e}ho zo slov typu $a^{2^n}$ alebo aj
akceptovanie nepr\'{\i}pustn\'{e}ho slova. Automat by sa dal zostroji\q
t aj jednoduch\v{s}ie, ale pri jeho zostavovan\'{\i} by sa musela
zachova\q t zv\'{y}\v{s}en\'{a} opatrnos\q t a taktie\v{z} d\^{o}kaz
funk\v{c}nosti by bol zrejme zlo\v{z}itej\v{s}\'{\i}.
\\

\par

Automat pracuje tak, \v{z}e si najsk\^{o}r vynuluje vstupn\'{u}
p\'{a}sku. Potom sa sna\v{z}\'{\i} cyklick\'{y}m duplikovan\'{\i}m
nan\'{a}\v{s}a\q t na p\'{a}sku slov\'{a} s d\'{l}\v{z}kou mocniny dva.
\v{C}i\v{z}e na p\'{a}ske sa postupne objavuj\'{u} slov\'{a} (lep\v{s}ie
povedan\'{e} prefixy) $a$, $a^2$, $a^4$, $a^8$ at\v{d}.
Samotn\'{e} cyklick\'{e} duplikovanie prefixu na p\'{a}ske prebieha tak, \v{z}e sa v
p\^{o}vodnom slove (prefixe) ozna\v{c}uj\'{u} u\v{z}
skop\'{\i}rovan\'{e} \v{c}asti slova. Pokia\q l s\'{u} v\v{s}etky
p\'{\i}smena slova prep\'{\i}san\'{e}, slovo sa znormalizuje a
pokra\v{c}uje sa v opatovnom kop\'{\i}rovan\'{\i}, tentoraz u\v{z}
v\v{s}ak nov\'{e}ho slova.
\\

\par

Detekcia spr\'{a}vnosti slova prebieha pri dosiahnut\'{\i} konca
p\'{a}sky. Pokia\q l slovo obsahuje nejak\'{e} p\'{\i}smen\'{a},
ktor\'{e} zatia\q l neboli skop\'{\i}rovan\'{e}, znamen\'{a} to, \v{z}e
slovo nie je tvaru $a^{2^n}$ a automat sa zasekne.  Pokia\q l boli
v\v{s}etky p\'{\i}smen\'{a} \'{u}spe\v{s}ne skop\'{\i}rovan\'{e},
znamen\'{a} to, \v{z}e slovo na p\'{a}ske je dvojn\'{a}sobkom
predch\'{a}dzaj\'{u}ceho slova (prefixu). Len\v{z}e toto slovo bolo
tvaru $a^{2^n}$. \v{C}i\v{z}e aj $a^{2^n.2}$ je tvaru $a^{2^n}$ a teda
automat slovo akceptuje.
\\

\par

Pravidl\'{a} $(01)-(05)$ sl\'{u}\v{z}ia na \'{u}vodn\'{e} vynulovanie
p\'{a}sky. \v{D}alej pravidl\'{a} $(11)-(18)$ zap\'{\i}\v{s}u $a'$ a
vykonaj\'{u} posun vpred. Kontrola, pr\'{\i}padne akcept\'{a}cia je
zabezpe\v{c}en\'{a} pomocou pravidiel $(21)-(26)$. Pravidl\'{a}
$(31)-(35)$ pret\'{a}\v{c}aj\'{u} vzad a nakoniec pravidl\'{a}
$(41)-(44)$ normalizuj\'{u} slovo (prefix).  \\

\section{D\^{o}kaz}

\underline{$L(A) \subseteq L$:}\\

\par

Chceme dok\'{a}za\q t, \v{z}e v\v{s}etky slov\'{a} akceptovan\'{e}
automatom $A$ patria do jazyka $L$.\\


\par

Ke\v{d}\v{z}e automat m\^{o}\v{z}e slovo akceptova\q t iba vtedy,
ke\v{d} s\'{u} u\v{z} v\v{s}etky p\'{\i}smen\'{a}
predch\'{a}dzaj\'{u}ceho slova skop\'{\i}rovan\'{e}, akceptovan\'{e}
bud\'{u} len slov\'{a} tvaru $a^{2^n}$.\\

\par

Akcept\'{a}cia slova in\'{e}ho
tvaru nie je mo\v{z}n\'{a} preto\v{z}e by to znamenalo, \v{z}e \v{c}ast
kop\'{\i}rovan\'{e}ho slova nebola skop\'{\i}rovan\'{a}. Na p\'{a}ske
ostalo aspo\v{n} jedno p\'{\i}smeno $a$. P\'{a}ska potom vyzer\'{a}
takto:
\begin{center}
	$\cent a'^*a^*b^*B^0\$$
\end{center}

\par
Kontroln\'{a} subrutina v\v{s}ak nedok\'{a}\v{z}e slovo akceptova\q t
pokia\q l obsahuje aspo\v{n} jedno p\'{\i}smeno $a$, \v{c}i\v{z}e
nespr\'{a}vna akcept\'{a}cia je vyl\'{u}\v{c}en\'{a}.




\underline{$L \subseteq L(A)$:}\\

\par
Chceme dok\'{a}za\q t, \v{z}e automat $A$ akceptuje v\v{s}etky slov\'{a} z
jazyka $L$. D\^{o}kaz vykon\'{a}me matematickou
indukciou vzh\q ladom na po\v{c}et rozhodovan\'{\i} v stave
$q_{determine}$.\\

\par
\begin{enumerate}
	\item[$1^\circ$] \v{L}ahko sa over\'{\i}, \v{z}e pri jednom
		rozhodovan\'{\i} v stave $q_{determine}$, bude automat $A$
		akceptova\q t slovo tvaru $\cent a\$ \in L$. Po \'{u}vodnom
		vy\v{c}isten\'{\i} p\'{a}sky a n\'{a}slednom zap\'{\i}san\'{\i}
		p\'{\i}smena $a'$, sa automat dostane do rozhodovacieho stavu pomocou
		$(11)$. N\'{a}sledne sa cez $(21)$ presunie do kontrolnej subrutiny
		pozost\'{a}vaj\'{u}cej zo stavov $q_{check_1}$ a $q_{check_2}$,
		ktor\'{a} slovo akceptuje.
		\\
		\par
		Podobne jednoducho sa d\'{a} overi\q t akcept\'{a}cia slova $\cent
		aa\$ \in L$, ktor\'{a} zodpoved\'{a} dvom ($2 = 2^{(1 - 1)} + 1$) rozhodovaniam v
		$q_{determine}$.
\item[$2^\circ$]
	Majme slovo tvaru $a^{2^n}$, ktor\'{e}mu zodpoved\'{a}
	$\sum_{i=0}^{n-1}2^i + 1$ rozhodovan\'{\i} v $q_{determine}$.
	Dok\'{a}\v{z}eme, \v{z}e slovu $a^{2^{(n+1)}}$ zodpoved\'{a}
	$\sum_{i=0}^{n}2^i + 1$ rozhodovan\'{\i} v $q_{determine}$. A naozaj.
	Slovo $a^{2^{n}}$ treba zdvojn\'{a}sobi\q t na p\'{a}ske.
	Ka\v{z}d\'{e} p\'{\i}smeno $a$ sa ozna\v{c}\'{\i} ako $a'$ a jeho
	k\'{o}pia v podobe p\'{\i}smena $b$ sa prenesie na koniec. Za
	ka\v{z}d\'{e} jedno kop\'{\i}rovan\'{e} p\'{\i}smeno nastane jedno
	rozhodovanie. \v{C}i\v{z}e po\v{c}et rozhodovan\'{\i} bude

\begin{center}
	$\sum_{i=0}^{n-1}2^i + 1 + |a^{2^{n}}| = \sum_{i=0}^{n-1}2^i + 1 + 2^n
	= 2^0 + 2^1 + 2^2 + \cdots + 2^n + 1 = \sum_{i=0}^{n}2^i + 1$
\end{center}

\par

Pri poslednom v z t\'{y}chto rozhodovan\'{\i} v\v{s}ak rozhodovac\'{\i}m
znakom pre pravidl\'{a} v $q_{determine}$ bude znak konca p\'{a}sky
$\$$, \v{c}i\v{z}e automat n\'{a}sledne slovo akceptuje.

\end{enumerate}


\par
Ke\v{d}\v{z}e $L(A) \subseteq L$ a z\'{a}rove\v{n} $L \subseteq L(A)$, tak potom
$L(A) = L$.

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

