\documentclass[12pt]{article}

\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{graphics}
\newcommand{\ra}{\ensuremath{\rightarrow}}


\setlength{\textheight}{26cm}

\setlength{\textwidth}{16cm}

\setlength{\baselineskip}{13pt}

\setlength{\topmargin}{-2.5cm}

\setlength{\oddsidemargin}{0.4cm}

\setlength{\evensidemargin}{0.4cm}

\pagestyle{empty}

\begin{document}
(a) Adj véges fordítót, ami minden $\{a,b\}$ feletti szót lefordít, 
mégpedig úgy, hogy az utoljára olvasott két karakter alapján ír ki. Ha ez a 
két betű $aa$ vagy $bb$, akkor nem ír semmit, ha $ab$, akkor $x$-et ír, 
különben $y$-t. Tehát pl. az $aabbaba$ fordítása $xyxy$.
\\ \ \ \\
(b) Ezzel a fordítóval lefordítjuk azt az $\{a,b\}$ feletti nyelvet, mely az
$a$-val kezdődő és végződő szavakat tartalmazza. Minél egyszerűbb osztályú
nyelvtan kell a lefordított nyelvre.
\\ \ \ \\
\noindent
{\bf A negyedik kis zh egy jó megoldása}
\\
\ \ 
\\
(a) A fordító automatája: 
\vspace*{.5cm}\\
\includegraphics{zh4mo1.eps}
\vspace*{.5cm}\\
Magyarázat:\\
$A$ állapotban vagyunk, ha $a$-t olvastunk utoljára, $B$-ben, ha $b$-t.
\\
\ \ \\
(b) Vegyük észre, hogy a lefordított szó lehet üres (ha csupa $a$ volt a 
fordítandó szóban) vagy pedig mindenképp $x$-szel kezdődik, hiszen az első
$b$ megjelenésekor kiírunk egy $x$-et. Mivel a szó $a$-ra végződik, 
a következő váltáskor, amikor $b$ után $a$ jön, kiírunk $y$-t. 
Innen ugyanígy folytatva, látható, hogy a lefordított szavak ${(xy)}^i$ alakúak
lesznek, $i\geq 0$-val. Kell még, hogy minden ilyen szó elő is áll. Már
láttuk, hogy az $\epsilon$ előáll fordításként, az  ${(xy)}^k$ szó pedig, 
ahol $k\geq 1$, kijön pl. az ${(ab)}^ka$ fordításaként. 
\\
Emiatt a nyelvtan: $S\ra xA\;|\;\epsilon$, $A\ra yS$.
Ez reguláris, a lehető legegyszerűbb. 
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
