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