IB102 ­ úkol 6 ­ řešení Odevzdání: 29. 10. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. Je zadán konečný automat:
GFED@ABC1
b
???????
GFED@ABC2
a
?? b
++GFED@ABC3

kk
b



//GFED@ABC4
a
OO

++GFED@ABC?>=<89:;5
a
kk
a
__??????????????????
* a) [2 body] zkonstruujte k němu ekvivalentní NFA bez -kroků a napište i množiny
D pro všechny stavy.
(Pokud nepoužijete standardní algoritmus, dokažte ekvivalenci původního automatu
se zkonstruovaným NFA bez -kroků).
* b) [0 bodů] nakreslete tento domeček jedním tahem (respektujte orientaci šipek, začít
můžete v libovolném stavu)
Řešení: a) Odstraněním -kroků získáme následující NFA:
GFED@ABC1
b
b
b
""
b
||
GFED@ABC2
EDGF
b
@A
//
a
88
b
++
b
??????????????????
b

GFED@ABC3
a,b
kk
GFED
b
BC
oo
a,b

a,b

a
__???????
//GFED@ABC?>=<89:;4
BC@A
a
GF
//
a
KK
a
++GFED@ABC?>=<89:;5
a
kk
a
__??????????????????
@ABC
a
ED
oo
a b
1  {2, 3, 4, 5}
2 {1} {2, 3, 4, 5}
3 {1, 2, 4, 5} {2, 3, 4, 5}
4 {2, 4, 5} 
 5 {2, 4, 5} 
D(1) = {1}
D(2) = {2}
D(3) = {2, 3, 4, 5}
D(4) = {4, 5}
D(5) = {5}
b) Například (číslo určuje pořadí, v jakém procházíme hrany):
GFED@ABC1
4
???????
GFED@ABC2
3
?? 9
++GFED@ABC3
10
kk
5

1

GFED@ABC4
2
OO
7
++GFED@ABC?>=<89:;5
6
kk
8
__??????????????????
IB102 ­ úkol 6 ­ řešení Odevzdání: 29. 10. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Mějme tři regulární výrazy r1, r2, r3. Je rozhodnutelné, zda konečný automat
ekvivalentní výrazu r3 akceptuje právě ta slova, které akceptuje automat ekvivalentní r1,
kromě slov akceptovaných automatem ekvivalentním r2? Pokud ano, popište algoritmus na
řešení problému (použijete-li algoritmy ze skript, nemusíte je podrobně popisovat). Pokud
ne, své tvrzení dokažte.
Řešení: Problém je rozhodnutelný následujícím algoritmem:
* Ke každému regulárnímu výrazu sestrojíme ekvivalentní konečný automat podle algoritmu
ze skript a převedeme je na DFA s totální přechodovou funkcí (Automaty
označíme A1, A2, A3).
* Sestrojíme automat co-A2, který získáme výměnou akceptujích stavů A2 za neakceptující
a obráceně.
* Synchronní paralelní kompozicí automatů A1 a co-A2 sestrojíme DFA A12.
* Minimalizujeme automaty A3 a A12, pak je převedeme do kanonického tvaru.
* Pokud jsou výsledné automaty identické, algoritmus vrátí ANO, jinak vrátí NE.