Formális nyelvek gyakorlat (5)

2001. március 13., kedd

1. Az alábbi kétirányú véges automatához kellene minimálautomatát adni:

$\delta(A,a)=(A,e)$
$\delta(A,b)=(B,e)$
$\delta(B,a)=(A,e)$
$\delta(B,b)=(B,h)$
Kezdõállapot az $A$, elfogadó állapotok az $A$ és a $B$.

2. Legyen egy kétirányú mozgást végzõ automata szabályrendszere a következõ:

$\delta(S,a)=(P,e)$
$\delta(S,b)=(Q,e)$
$\delta(P,a)=(P,e)$
$\delta(P,b)=(Q,e)$
$\delta(Q,a)=(S,h)$
$\delta(Q,b)=(S,e)$
Kezdõállapot az S, elfogadó állapotok az S és a P. Készítsen minimálautomatát a fenti automata által elfogadott nyelvre!

3. Adott az alábbi kétirányban mozgó véges automata:

$\delta(S,a)=(P,e)$
$\delta(S,b)=(Q,e)$
$\delta(R,a)=(V,h)$
$\delta(R,b)=(V,h)$
$\delta(P,a)=(R,e)$
$\delta(P,b)=(Q,e)$
$\delta(T,a)=(V,h)$
$\delta(T,b)=(V,h)$
$\delta(Q,a)=(S,h)$
$\delta(Q,b)=(T,e)$
$\delta(V,a)=(S,e)$
$\delta(V,b)=(S,e)$ Valamennyi állapot elfogadó állapot. Készítsen az automata által elfogadott nyelvre minimálautomatát!

4. HF, írásban Milyen nyelvet fogad el az alábbi kétirányú véges automata?

$\delta(q_0,a)$	=	$(q_0,e)$	$\delta(q_0,b)$	=	$(q_1,h)$
$\delta(q_1,a)$	=	$(q_2,e)$	$\delta(q_1,b)$	=	$(q_3,h)$
$\delta(q_2,a)$	=	$(q_3,h)$	$\delta(q_2,b)$	=	$(q_0,e)$
$\delta(q_3,a)$	=	$(q_3,h)$	$\delta(q_3,b)$	=	$(q_3,h)$

Elfogadó állapot a $q_0$.

5. Tekintsük az alábbi két nyelvet: $L=\{A,B,\ldots, Z, a,b, \ldots, z\}$ és $D=\{0,1,2,\ldots, 9\}$.
Fogalmazd meg szavakkal, hogy mely szavakból állnak az alábbi nyelvek:
$L\cup D$, $LD$, $L^4$, $L^*$, $L{(L\cup D)}^*$, $D^+$.

6. Fogalmazd meg szavakkal, hogy mik az alábbi reguláris kifejezések által leírt nyelvek:
$0{(0+1)}^*0$, ${(0+1)}^*0{(0+1)}{(0+1)}$, $0^*10^*10^*10^*$, ${(a+b)}^*(aa+bb){(a+b)}^*$, ${(a^*+b^*)}^*$

7. Add meg reguláris kifejezéssel az alábbi $\Sigma=\{a,b\}$ feletti nyelveket:
(a) $\{w\in {\Sigma}^*\;\vert\;$ w-ben van legalább két a$\}$
(b) $\{w\in {\Sigma}^*\;\vert\;$ w-ben minden teljes homogén a-részsorozat páros és minden teljes homogén b-részsorozat páros $\}$
(c) $\{w\in {\Sigma}^*\;\vert\;$ van olyan betû amibõl $\geq 2$ van w-ben$\}$
(d) $\{w\in {\Sigma}^*\;\vert\;$ w-ben minden teljes homogén a-részsorozat páros és minden teljes homogén b-részsorozat páratlan $\}$