% (c) 2002 Ondrej Jombik % 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}