IB102 ­ úkol 6 Odevzdání: 29. 10. 2008
Vypracoval(a): UČO:
Skupina:
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)
IB102 ­ úkol 6 Odevzdání: 29. 10. 2008
Vypracoval(a): UČO:
Skupina:
2. [2 body] Mějme tři regulární výrazy r1, r2, r3 nad abecedou . 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.