Gyakorló feladatok formális nyelvekbõl 3. gyakorlat 1. Az L nyelv mondatainak hossza osztható hárommal, az üres szó nincs a nyelvben. Ezek szerint egy tetszõleges mondatának karaktereit hármasával csoportokra oszthatjuk (az elejérõl kezdve). Minden csoportban valamelyik karakter legalább kétszer elõfordul. A nyelv szavaira az igaz, hogy ez a többségi karakter a szomszédos csoportokban egymástól különbözik. Szerkesszen minimálautomatát a fenti nyelvre! 2. Az L nyelv szavaiban a szavak nem ugyanazzal a betûvel kezdõdnek, mint amivel végzõdnek, így páros számú homogén részsorozat van minden szóban. Párosítva ezeket (az elsõt a másodikkal, a harmadikat a negyedikkel, stb.), minden pár hossza páratlan, tehát a pár egyik tagja páros a másik meg páratlan. Adjunk az L nyelvhez minimálautomatát! 3. Álljon az L nyelv $\{a,b\}^*$ azon szavaiból, melyek ha a-ra végzõdnek, akkor nen tartalmaznak bb részszót, és ha b-re végzõdnek, akkor nem tartalmaznak aa részszót. Készíts minimálautomatát ehhez a nyelvhez! 4. Adott az alábbi kétirányban mozgó véges automata: $\delta(P,a)=(Q,e)$ $\delta(P,b)=(R,e)$ $\delta(Q,a)=(U,e)$ $\delta(Q,b)=(W,h)$ $\delta(R,a)=(P,h)$ $\delta(R,b)=(V,e)$ $\delta(U,a)=(W,h)$ $\delta(U,b)=(Q,h)$ $\delta(V,a)=(W,h)$ $\delta(V,b)=(W,h)$ $\delta(W,a)=(P,e)$ $\delta(W,b)=(P,e)$ Elfogadó állapotok a Q és a V. Készítsen az automata által elfogadott nyelvre egyirányban mozgó véges automatát és írja le vverbálisan, hogy mi a generált nyelv! Adja meg a nyelvet reguláris kifejezéssel is!