% Ondrej Jombik % [26/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 \font\brm = cmr10 scaled \magstep 1 \font\bbrm = cmr10 scaled \magstep 2 \font\bbbrm = cmr10 scaled \magstep 3 \font\bbbbrm = cmr10 scaled \magstep 4 \font\bbbbbrm = cmr10 scaled \magstep 5 \begin{document} \hsize = 4 in \parindent = 0 pt \leftskip = 1 in % PAGE 1 \begin{center} \brm \bigskip \bigskip \bigskip \bigskip \bigskip Form{\ad}lne jazyky a automaty\\ \bigskip \bigskip \bigskip \bigskip \bigskip {\Ud}loha 4\\ \smallskip Sada 1\\ \bigskip \bigskip \bigskip \bigskip \bigskip \rm Ondrej Jomb{\id}k\\ 2i2 \end{center} %\eject % PAGE 2 \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \section{Zadanie} \bigskip \bigskip \bigskip \bigskip \bigskip \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} \begin{center} L = L(G). \end{center} \eject % PAGE 3 \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \section{Defin{\id}cie} \bigskip \bigskip \bigskip \par \underline{Defin{\id}cia:} Kontextov{\ad} gramatika je tak{\ad} fr{\ad}zov{\ad} gramatika, v ktorej pre ka{\zm}d{\ed} pravidlo $u \Rightarrow v$ plat{\id} $|u| \leq |v|$. \bigskip \bigskip \bigskip \par \underline{Defin{\id}cia:} Fr{\ad}zov{\ad} gramatika je {\sm}tvorica \begin{center} G=(N, T, P, $\sigma$), \end{center} kde N a T s{\ud} abecedy netermin{\ad}lnych a termin{\ad}lnych symbolov (N $\cap$ T = $\not 0$), $\sigma \in$ N je po{\cm}iato{\cm}n{\yd} netermin{\ad}l a {P $\subseteq$ (N $\cup$ T )$^*$N(N $\cup$ T)$^*$ $\times$ (N $\cup$ T)$^*$} je kone{\cm}n{\ad} mno{\zm}ina pravidiel. %\eject % PAGE 4 \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \section{{\Ud}vahy} \par 1. $ww^R$ vieme vygenerova{\tm} jednoducho\\ 2. pre $ww^Rw$ ozna{\cm}{\id}me koniec slova\\ 3. vytvor{\id}me netermin{\ad}ly\\ 4. generujeme {\sm}peci{\ad}lne $ww^R$\\ 5. posun netermin{\ad}lov na koniec\\ 6. konverzia na termin{\ad}ly\\ 7. z{\ad}mena koncov{\ed}ho znaku\\ 8. $ww^Rw$ \eject % PAGE 5 \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \section{Rie{\sm}enie} \par \underline{G=(N, T, P, $\sigma$)} \\\\ N=$\{X_1, X_2, T_1, T_2, A, B, \sigma\}$\\ T=$\{a, b\}$\\ P=$\left\{ \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}\right\}$ %\eject % PAGE 6 \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \section{D\^okaz (1.{\cm}as{\tm})} \par L(G) $\subseteq$ L: odvodzovanim pod{\lm}a P \\ \par 1. $p_{10}, p_{11}$: po{\cm}iato{\cm}n{\yd} krok, zap{\id}{\sm}eme $T_i$\\ 2. $p_{20}, p_{21}$: z{\ad}pis 2 termin{\ad}lov a 1 netermin{\ad}lu\\ 3. $p_{30}, ..., p_{33}$: presun netermin{\ad}lov na koniec slova\\ 4. $p_{40}, ..., p_{43}$: transformacia krajn{\yd}ch netermin{\ad}lov na termin{\ad}ly; mo{\zm}nos{\tm} n{\ad}vratu na (3)\\ 5. $p_{50}, p_{51}$: fin{\ad}lna konverzia\\ 6. vysledn{\ed} slovo v tvare $ww^Rw$ \eject % PAGE 7 \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \section{D\^okaz (2.{\cm}as{\tm})} \par L $\subseteq$ L(G): MI vzh{\lm}adom na d{\ld}{\zm}ku slova \\ \par {\bf $1^\circ$} $\sigma\Rightarrow_{(p_{10}|p_{11})} X_1T_1 \Rightarrow_{(p_{20}|p_{21})} xxx = u$ \\ \\ {\bf $2^\circ$} \underline{ $u=ww^Rw$ } \\ $\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$ \\ \\ \underline{ $u'=wxxw^Rwx$ } \\ $\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'$ \bigskip \bigskip \bigskip \bigskip \bigskip \bigskip \section{Z{\ad}ver} \bigskip \bigskip \par L(G)$\subseteq$L $\wedge$ L$\subseteq$L(G) $\Rightarrow$ L(G)=L \bigskip \bigskip \par {\Ud}lohu sa mi podarilo {\ud}spe{\sm}ne vyrie{\sm}i{\tm} a dok{\ad}za{\tm}. \end{document}