IB102 ­ úkol 5 ­ řešení Odevzdání: 20. 10. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Nechť L je jazyk nad abecedou  a w  
. Definujme následující operaci:
w/L = {u | wu  L}
Například pro L = {ab, aba, bba} platí ab/L = {, a}.
Bez využití převodu na DFA uvedťe obecný postup, kterým lze pro libovolný nedeterministický
konečný automat M bez -kroků a slovo w sestrojit automat M (bez -kroků),
pro který platí L(M ) = w/L(M). Tím dokážeme, že je třída regulárních jazyků uzavřena
na operaci w/L pro každé w. Zdůvodněte správnost své konstrukce.
Řešení: Nechť M = (Q, , , q0, F). Slovo wu patří do L právě tehdy, platí-li ^(q0, wu)F =
, což můžeme přepsat jako p^(q0,w)
^(p, u)  F = . To znamená, že w určuje nějakou
množinu stavů A = ^(q0, w), kde pokud by jeden z těchto stavů byl počáteční, automat M
by akceptoval slovo u. Protože nemůžeme použít více počátečních stavů ani -kroky, musíme
přidat nový iniciální stav, který bude ekvivalentní všem stavům v této množině, tzn. budou
z něj vést přechody do stejných stavů a bude koncový, pokud alespoň jeden stav množiny A
je koncový:
M = (Q  {qi}, ,  , qi, F ), kde qi / Q,
 (q, a) =
(q, a) pokud q  Q
pA (p, a) pokud q = qi
,
F =
F  {qi} pokud A  F = 
F jinak
IB102 ­ úkol 5 ­ řešení Odevzdání: 20. 10. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] K zadanému nedeterministickému konečnému automatu zkonstruujte ekvivalentní
minimální konečný automat v kanonickém tvaru. Konstrukci zde uvedťe.
a b
 1 {2, 3, 4} {3, 4}
 2 {2, 3} {3, 4}
3  {3, 4, 5}
4 {5} {4, 5}
5  
Řešení: Aplikací algoritmu pro transformaci NFA na ekvivalentní DFA dostáváme:
a b
 {1} {2, 3, 4} {3, 4}
 {2, 3, 4} {2, 3, 5} {3, 4, 5}
{3, 4} {5} {3, 4, 5}
 {2, 3, 5} {2, 3} {3, 4, 5}
{3, 4, 5} {5} {3, 4, 5}
{5}  
 {2, 3} {2, 3} {3, 4, 5}
  
Tento automat je zřejmě bez nedosažitelných stavů a s totální přechodovou funkcí.
Konstrukce minimálního automatu:
0 a b
I  {1} II I
{3, 4} I I
{3, 4, 5} I I
{5} I I
 I I
II  {2, 3, 4} II I
 {2, 3, 5} II I
 {2, 3} II I
1 a b
I  {1} III II
II {3, 4} II II
{3, 4, 5} II II
{5} II II
 II II
III  {2, 3, 4} III II
 {2, 3, 5} III II
 {2, 3} III II
Minimální automat tedy je:
a b
 I III II
II II II
 III III II
Nakonec převedeme minimální automat do kanonického tvaru:
a b
 A B C
 B B C
C C C