\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 nagy zh egy jó megoldása}
\\
\ \ 
\\
1. Az alábbi automata jó lesz: 
\vspace*{.5cm}\\
\includegraphics{nzhmo1.eps}
\vspace*{.5cm}\\
Az állapotok jelentései, ebből adódik, hogy mért jó az automata: \\
$S$: még nem olvastunk semmit\\
$T$ nulla a szám eleje, azaz biztos elutasítunk\\
$A$: az első jegy 1\\
$B$: az első jegy 2-9 \\
$C$: a szám eleje 10 vagy 11, tehát még legalább két karakter kell az 
elfogadáshoz\\
$D$: a szám eleje 12, azaz szét kell majd választani két esetet a következő 
karakter szerint\\
$E$: a szám eleje 13, azaz elég már egy karakter az elfogadáshoz\\
$F$: az első 3 jegy $\leq$ 124, azaz még egy karakter kell biztosan\\
$G$ : elfogadó, vagy $>124$ háromjegyű szám jött, vagy egy legalább négyjegyű
\\
Ez determinisztikus és egy kezdőállapotú, szóval pont, amilyen kell.
\\
\ \ \\
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 (A,{\D}_1)=Q_1$, ahol ${\D}_1=A,A, \dagger$
\\
$(Q_0,b)\ra (B,{\D}_2)=Q_2$, ahol ${\D}_2=B,\dagger,A$
\\
$(Q_1,a)\ra (A,{\D}_1)=Q_1$ 
\\
$(Q_1,b)\ra \dagger$
\\
$(Q_2,a)\ra (A,{\D}_3)=Q_3$, ahol ${\D}_3=A,A,A$
\\
$(Q_2,b)\ra (A,{\D}_2)=Q_4$ 
\\
$(Q_3,a)\ra (A,{\D}_3)=Q_3$
\\
$(Q_3,b)\ra \dagger$
\\
$(Q_4,a)\ra (A,{\D}_3)=Q_3$
\\
$(Q_4,b)\ra \dagger$
\\
Tehát az egyirányú automata, ami determinisztikus és egy kezdőállapotú:
\vspace*{.5cm}\\
\includegraphics{nzhmo2.eps}
\vspace*{.5cm}\\
\ \ \\
3. Először megfordítjuk a nyelvtant:\\
\begin{tabbing} 
\hspace*{2cm}\=$S\ra 1A$\=$\;|\;1B$\\ 
\>$A\ra 1S$\>$\;|\;\epsilon$\\ 
\>$B\ra 0B$\>$\;|\;1A\;|\;0A$ 
\end{tabbing}   
Ezután konstruálunk véges automatát ehhez a megfordított
nyelvtanhoz:
\vspace*{.5cm}\\
\includegraphics{nzhmo3.eps}
\vspace*{.5cm}\\
Ezután ezt az automatát visszafordítjuk, azaz a régi kezdőállapot lesz most 
az elfogadó, a régi elfogadó állapot a kezdő és minden nyilat fordítva húzunk
be:
\vspace*{.5cm}\\
\includegraphics{nzhmo4.eps}
\vspace*{.5cm}\\
Ezt determinizáljuk és teljesen specifikáljuk:\\
\vspace*{.5cm}\\
\includegraphics{nzhmo5.eps}
\vspace*{.5cm}\\
Ezt még minimalizáljuk, mivel minimálautomata kell:
\\
A=1, B=2, SB=3, S=4, SA=5, SAB=6, T=7 számozással:\\
$127\;\;\;||\;\;\;3456$\\ 
$12\;\;||\;\;7\;\;||\;4\;\;\;||356$\\ 
$1\;\;||\;\;2\;\;||\;\;7\;\;||\;4\;\;\;||356$\\ 
És ez már nem változik, tehát a minimálautomata:
\vspace*{.5cm}\\
\includegraphics{nzhmo6.eps}
\vspace*{.5cm}\\
\ \ \\
4. 
Először minimálautomatát adunk az első reguláris kifejezéshez:\\
az $a{(ba)}^*+ba$-hoz tartozó automata:\\
\vspace*{.5cm}\\
\includegraphics{nzhmo7.eps}
\vspace*{.5cm}\\
Magyarázat ehhez: \\
$A$-ban vagyunk, ha $a{(ba)}^*$ alakú szó jött eddig\\
$B$-ben vagyunk, ha $a{(ba)}^*b$ alakú szó jött eddig\\
$C$-ben vagyunk, ha egy darab b jött eddig\\
$A$-ban vagyunk, ha egy darab ab jött eddig\\
Ebből a tranzitív lezárt automatája, behúzva $\epsilon$-nyilakat $D$-ből és
$A$-ból $S$-be és $S$-et elfogadóvá téve 
(nem kell új kezdőállapot, mivel a régi kezdőbe nem vezet 
vissza nyíl):
\vspace*{.5cm}\\
\includegraphics{nzhmo8.eps}
\vspace*{.5cm}\\
Az $\epsilon$-szabályokat kiküszöbölve:
\vspace*{.5cm}\\
\includegraphics{nzhmo9.eps}
\vspace*{.5cm}\\
Ezt determinizálva és teljesen specifikálva:\\
\vspace*{.5cm}\\
\includegraphics{nzhmo10.eps}
\vspace*{.5cm}\\
Minimalizálva azt kapjuk, hogy az elfogadók összevonhatók és az 
elutasítók is, kivéve a csapdát.
\\
Így lesz a következő automata:
\vspace*{.5cm}\\
\includegraphics{nzhmo11.eps}
\vspace*{.5cm}\\
Vagyis az első reguláris kifejezés azokat a szavakat írja le, melyekben minden 
$b$ után jönnie kell közvetlenül legalább egy $a$-nak. Másszóval amely szavakban
nincs kettő $b$ egymás után és ahol a szavak nem is végződhetnek $b$-re.
\\
Megmutatjuk, hogy a második reg. kif. is pont ezeket a szavakat írja le.
 \\
Vegyük észre, hogy a második reg. kif. ugyanaz, mint $a^*{(baa^*)}^*$, hiszen 
$\epsilon$ része $a^*$-nak és  $a^*{(baa^*)}^*$-nak is.
\\
Az $a^*{(baa^*)}^*$ által leírt szavakban nem állhat két $b$ egymás után, mert
minden $b$-t követ legalább egy $a$ és ugyanezért $b$-re se végződhetnek a 
szavak. Másrészt minden olyan szót, amiben nincs két $b$ egymás után és ami nem
végződik $b$-re leír az $a^*{(baa^*)}^*$ kifejezés, hiszen akárhány $b$-t és a 
$b$-k után akárhány $a$-t le tudunk tenni.
\\
Tehát a két reg. kif. azonos nyelvet ad meg.
\\
\ \ \\
5. Az $L_1$ nyelv reguláris, amit az alábbi véges automata bizonyít:
\vspace*{.5cm}\\
\includegraphics{nzhmo12.eps}
\vspace*{.5cm}\\
Az állapotok jelentése a következő:\\
$S$: eddig pont ugyanannyi $a$ volt, mint $b$\\
$A$: eddig eggyel több $a$ volt, mint $b$\\
$B$: eddig eggyel több $b$ volt, mint $a$\\
$C$: eddig kettővel több $a$ volt, mint $b$\\
$D$: eddig kettővel  több $b$ volt, mint $a$\\
$T$ : volt már rossz kezdőszelet, ahol túl nagy volt a különbség, innen már sose
fogadunk el, azaz csapda
\\
Ez az automata pont a kívánt nyelvet fogadja el, hiszen csak arra 
kell figyelni, hogy az eddig beolvasott szóban az $a$-k és $b$-k számának 
különbsége 0, 1, 2, vagy több.
\\
Az $L_2$ nyelv azonban nem reguláris, ezt a pumpálási lemmával igazoljuk.
Ha $L_2$ reguláris lenne, akkor létezne egy olyan $p$ szám, ami a lemmában
van. Vegyük ezen $p$-vel az $a^pb^p$ szót. Ez a szó $L_2$-ben van és 
hosszabb $p$-nél. Jelöljük ki benne az $a^p$ részszó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 $a^p$-ben csak csupa $a$-ból álló részszót tudunk találni, ha pedig azt 
több, mint 3-szor megismételjük, akkor biztos több mint kettővel több
lesz az $a$-k száma a szóban, mint a $b$-k száma.

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