Formális nyelvek pótzárthelyi 2001. április 17. 1. Adj minimálautomatát a tizes számrendszerben felírt, 3-mal osztható természetes számokat tartalmazó nyelvre! Egy természetes szám nem kezdõdhet nullával, kivéve ha õ maga a 0 szám. 2. Adj meg egy egyirányban mozgó, egy kezdõállapottal rendelkezõ, determinisztikus véges automatát, mely egyenértékû az alábbi kétirányban mozgó véges automatával (vagyis ugyanazt a nyelvet fogadja el)! $\delta(S,a)=(A,h)$ $\delta(S,b)=(B,e)$ $\delta(A,a)=(A,h)$$\delta(A,b)=(B,e)$ $\delta(B,a)=(S,e)$$\delta(B,b)=(A,e)$ Kezdõállapot az $S$, elfogadó állapot az $A$, $e$ jelentése: elõre, $h$ jelentése: hátra. 3. Add meg reguláris kifejezéssel az alábbi nyelvtan által generált nyelv komplementerét! $S\ensuremath{\rightarrow}aS$$\;\vert\;bA\;\vert\;bB\;\vert\;b$ $A\ensuremath{\rightarrow}aA$$\;\vert\;aS\;\vert\;bS\;\vert\;a$ $B\ensuremath{\rightarrow}aA$$\;\vert\;bB\;\vert\;\epsilon$ (Itt az utolsó sorban lemaradt a B--> a szabály, de emiatt nem akarom újrafordítani az egészet. Vegyétek úgy, hogy oda van írva.) 4. Adj egy darab kezdõállapottal rendelkezõ, determinisztikus véges automatát és reguláris kifejezést az alábbi nyelvhez: $L=\{\;w\in {\{\;0,1\;\}}^*\;\vert\; w$-ben páros sok 1-es van, és $w$-ben nem fordul elõ részszóként a $010\;\}$ 5. Döntsd el, hogy reguláris-e a következõ nyelv! $L=\{\;a^{2^n}\;\vert\; n\geq 0\;\}$ Azaz a nyelvben a 2-hatvány darab a-ból álló szavak vannak. Mindegyik feladat 6 pontot ér. Válaszaidat mindig indokold meg, magyarázat nélküli megoldásokat nem fogadunk el. Jó munkát! Megoldás