A nagy zh egy jó megoldása 1. Az alábbi automata jó lesz: 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)\ensuremath{\rightarrow}(A,{\ensuremath{\Delta}}_1)=Q_1$, ahol ${\ensuremath{\Delta}}_1=A,A, \dagger$ $(Q_0,b)\ensuremath{\rightarrow}(B,{\ensuremath{\Delta}}_2)=Q_2$, ahol ${\ensuremath{\Delta}}_2=B,\dagger,A$ $(Q_1,a)\ensuremath{\rightarrow}(A,{\ensuremath{\Delta}}_1)=Q_1$ $(Q_1,b)\ensuremath{\rightarrow}\dagger$ $(Q_2,a)\ensuremath{\rightarrow}(A,{\ensuremath{\Delta}}_3)=Q_3$, ahol ${\ensuremath{\Delta}}_3=A,A,A$ $(Q_2,b)\ensuremath{\rightarrow}(A,{\ensuremath{\Delta}}_2)=Q_4$ $(Q_3,a)\ensuremath{\rightarrow}(A,{\ensuremath{\Delta}}_3)=Q_3$ $(Q_3,b)\ensuremath{\rightarrow}\dagger$ $(Q_4,a)\ensuremath{\rightarrow}(A,{\ensuremath{\Delta}}_3)=Q_3$ $(Q_4,b)\ensuremath{\rightarrow}\dagger$ Tehát az egyirányú automata, ami determinisztikus és egy kezdõállapotú: 3. Elõször megfordítjuk a nyelvtant: $S\ensuremath{\rightarrow}1A$$\;\vert\;1B$ $A\ensuremath{\rightarrow}1S$ $\;\vert\;\epsilon$ $B\ensuremath{\rightarrow}0B$ $\;\vert\;1A\;\vert\;0A$ Ezután konstruálunk véges automatát ehhez a megfordított nyelvtanhoz: 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: Ezt determinizáljuk és teljesen specifikáljuk: 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\;\;\;\vert\vert\;\;\;3456$ $12\;\;\vert\vert\;\;7\;\;\vert\vert\;4\;\;\;\vert\vert 356$ $1\;\;\vert\vert\;\;2\;\;\vert\vert\;\;7\;\;\vert\vert\;4\;\;\;\vert\vert 356$ És ez már nem változik, tehát a minimálautomata: 4. Elõször minimálautomatát adunk az elsõ reguláris kifejezéshez: az $a{(ba)}^*+ba$-hoz tartozó automata: 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): Az $\epsilon$-szabályokat kiküszöbölve: Ezt determinizálva és teljesen specifikálva: 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: 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: 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.