\documentclass[12pt]{article}

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


\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}
\noindent
{\bf A pót zh egy jó megoldása}
\\
\ \ 
\\
1. Az alábbi automata jó lesz: 
\vspace*{.5cm}\\
\includegraphics{potzhmo1.eps}
\vspace*{.5cm}\\
Az állapotok jelentései, ebből adódik, hogy mért jó az automata: \\
$S$: még nem olvastunk semmit\\
$OK$: nulla a szám eleje, az egy nulla az jó\\
$T$ nulla után jön még más is, azaz biztos elutasítunk\\
$1$: az eddigi maradék 1\\
$2$: az eddigi maradék 2\\
$3$: az eddigi maradék 0\\
\\
Itt végülis azt nézzük az állapotokban, hogy az eddig beolvasott szám mennyi
maradékot ad 3-mal osztva. 
A következő számjegy beolvasásakor egyszerűen csak össze
kell adni az eddigi maradékot a számmal, ami jött és mod 3 nézni az eredményt.
\\
\ \ \\
Ez minimális lesz, mert \\
$ST12\;\;\;||\;\;\;OK\;\;3$\\ 
$S\;\;||\;\;T\;\;||\;1\;\;\;||2\;\;\;||\;OK\;\;\;||3\\ $
Azaz egy lépésben szétesnek az osztályok.
\\
\ \ \\
2. Az órán tanult algoritmus szerint eljárva:\\
$Q_0=(S,{\Delta}_0)$, ahol ${\Delta}_0=\dagger, \dagger, \dagger$\\
(A falaknál a visszatérő állapotokat $S,A,B$ sorrendben sorolom fel, tehát
az első helyen áll az $S$-hez, aztán az $A$-hoz, végül pedig a $B$-hez 
tartozó visszatérő állapot.)
\\
\ \ \\
$(Q_0,a)\ra \dagger$
\\
$(Q_0,b)\ra (B,{\D}_1)=Q_1$, ahol ${\D}_1=B,B,A$
\\
$(Q_1,a)\ra (S,{\D}_2)=Q_2$, ahol ${\D}_2=S,S,S$ 
\\
$(Q_1,b)\ra (A,{\D}_1)=Q_3$ 
\\
$(Q_2,a)\ra  \dagger$
\\
$(Q_2,b)\ra (B,{\D}_1)=Q_1$ 
\\
$(Q_3,a)\ra (S,{\D}_2)=Q_2$
\\
$(Q_3,b)\ra (B,{\D}_1)=Q_1$
\\
\ \ \\
Tehát az egyirányú automata, ami determinisztikus és egy kezdőállapotú:
\vspace*{.5cm}\\
\includegraphics{potzhmo2.eps}
\vspace*{.5cm}\\
\ \ \\
3. Először felrajzoljuk a nyelvtanból az automatát:\\
\vspace*{.5cm}\\
\includegraphics{potzhmo3.eps}
\vspace*{.5cm}\\
Ezt determinizáljuk és teljesen specifikáljuk:\\
\vspace*{.5cm}\\
\includegraphics{potzhmo4.eps}
\vspace*{.5cm}\\
Ezt még minimalizáljuk, mivel minimálautomata kell. Észrevesszük, hogy
az összes elfogadó állapot egybevonható, mivel ezekből soha nem térünk
vissza S-be:
\vspace*{.5cm}\\
\includegraphics{potzhmo5.eps}
\vspace*{.5cm}\\
Ennek komplementerét véve:
\vspace*{.5cm}\\
\includegraphics{potzhmo6.eps}
\vspace*{.5cm}\\
A reguláris kifejezés innen adódik: $a^*$.
\\
\ \ \\
4. 
Egy jó automata:
\vspace*{.5cm}\\
\includegraphics{potzhmo7.eps}
\vspace*{.5cm}\\
Magyarázat ehhez: \\
$1S$-ben vagyunk, ha páros sok $1$ jött eddig és utoljára se $0$-t, se 
$01$-t nem olvastunk és $010$ még nem volt\\ 
$1T$-ben vagyunk, ha páratlan sok $1$ jött eddig és utoljára se $0$-t, se 
$01$-t nem olvastunk és $010$ még nem volt\\ 
$0S$-ben vagyunk, ha páros sok $1$ jött eddig és utoljára $0$-t olvastunk
és $010$ még nem volt\\ 
$0T$-ben vagyunk, ha páratlan sok $1$ jött eddig és utoljára $0$-t olvastunk
és $010$ még nem volt\\ 
$01S$-ben vagyunk, ha páros sok $1$ jött eddig és utoljára $01$-t olvastunk
és $010$ még nem volt\\ 
$01T$-ben vagyunk, ha páratlan sok $1$ jött eddig és utoljára $01$-t olvastunk
és $010$ még nem volt\\ 
$T$-ben vagyunk, ha volt már $010$ \\ 
\ \ \\
A reguláris kifejezés egyenletek felírásával:\\
$1S=A, 1T=C, 0S=B, 0T=E, 01T=D, 01S=G$ átírással és a csapda lehagyásával:
\\
$A=0B+1C+\epsilon$\\
$B=0B+1D+\epsilon$\\
$C=0E+1A$\\
$D= 1A$\\
$E=0E+1G$\\
$G=1C+\epsilon$\\
\ \ \\
Innen: \\
$E=0E+11C+1$, majd $E=0^*(11C+1)$\\
illetve\\
$B=0B+11A+\epsilon$, majd $B=0^*(11A+\epsilon)$\\
\ \ \\
Az elsőt a $C$-s egyenletbe beírva:\\
$C=00^*(11C+1)+1A$, azaz $C={(0^+11)}^*(0^+1+1A)$.
\\
\ \ \\
Ezt és a második egyenletet az $A$-s eredeti egyenletbe visszaírva:
\\
$A=00^*(11A+\epsilon)+1{(0^+11)}^*(0^+1+1A)+\epsilon$, ahonnan
\\
$A={(0^+11+1{(0^+11)}^*1)}^*(0^++1{(0^+11)}^*0^+1+\epsilon)$ 
\\
\ \ \\
5. Az $L$ nyelv nem reguláris, ezt a pumpálási lemmával igazoljuk.
Ha $L$ reguláris lenne, akkor létezne egy olyan $p$ szám, ami a lemmában
van. Vegyün  ezen $p$-vel az $a^{2^p}$ szót. Ez a szó $L$-ben van és 
hosszabb $p$-nél. Jelöljük ki benne az $a^p$ kezdőszeletet, vagyis az 
első $p$ a-betűt. Mivel ez sem rövidebb 
$p$-nél, a lemma miatt ebben kell tudnunk találni egy olyan részszót, melyet
lehet ismételgetni úgy, hogy még mindig a nyelvben maradunk.
De ha itt pumpálunk, akkor az első pumpálásnál, amikor kétszer ismétlejük meg
a pumpálandó részszót a szó hossza $2^p$ és $2^p+p$ között lesz. Ez a hossz
biztosan nem kettô-hatvány, vagyis kikerültünk a nylevből, mégsem lehet
pumpálni. 


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