A pót 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 $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\;\;\;\vert\vert\;\;\;OK\;\;3$ $S\;\;\vert\vert\;\;T\;\;\vert\vert\;1\;\;\;\vert\vert 2\;\;\;\vert\vert\;OK\;\;\;\vert\vert 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)\ensuremath{\rightarrow}\dagger$ $(Q_0,b)\ensuremath{\rightarrow}(B,{\ensuremath{\Delta}}_1)=Q_1$, ahol ${\ensuremath{\Delta}}_1=B,B,A$ $(Q_1,a)\ensuremath{\rightarrow}(S,{\ensuremath{\Delta}}_2)=Q_2$, ahol ${\ensuremath{\Delta}}_2=S,S,S$ $(Q_1,b)\ensuremath{\rightarrow}(A,{\ensuremath{\Delta}}_1)=Q_3$ $(Q_2,a)\ensuremath{\rightarrow}\dagger$ $(Q_2,b)\ensuremath{\rightarrow}(B,{\ensuremath{\Delta}}_1)=Q_1$ $(Q_3,a)\ensuremath{\rightarrow}(S,{\ensuremath{\Delta}}_2)=Q_2$ $(Q_3,b)\ensuremath{\rightarrow}(B,{\ensuremath{\Delta}}_1)=Q_1$ Tehát az egyirányú automata, ami determinisztikus és egy kezdõállapotú: 3. Elõször felrajzoljuk a nyelvtanból az automatát: Ezt determinizáljuk és teljesen specifikáljuk: 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: Ennek komplementerét véve: A reguláris kifejezés innen adódik: $a^*$. 4. Egy jó automata: 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.