Minimální automat
Deterministický konečný automat M s totální přechodovou funkcí nazveme minimální konečný automat pro jazyk L(M), neexistuje-li ekvivalentní DFA s totální přechodovou funkcí a menším počtem stavů.
Důsledek 2.31. Minimální konečný automat akceptující regulární jazyk L je určen jednoznačně až na isomorfismus (tj. přejmenování stavů).
Důkaz, plyne přímo z Myhillovy-Nerodovy věty. □
IB102 Automaty, gramatiky a složitost, 3.10.2016
1/32
Konstrukce minimálního konečného automatu
Definice 2.18. Nechť M = (q, 51,5, q0, F) je DFA. Stav q e Q nazveme dosažitelný, pokud existuje i^gP takové, že S(q0, w) = q. Stav je nedosažitelný, pokud není dosažitelný.
IB102 Automaty, gramatiky a složitost, 3.10.2016
2/32
Příklad
Algoritmus pro eliminaci nedosažitelných stavů DFA
Vstup:   Deterministický konečný automat M = (Q, Z, S, q0, F). Výstup: Ekvivalentní automat M' bez nedosažitelných stavů.
1: / := 0
2: Si := {Qo}
3: repeat
4:     S/+1 := Si u {q I 3p e Sj, a e Z : <5(p, a) = g}
5:      / := /' + 1 6: until Si = S/_i 7: Q' := S/
8: M' :=(0',I)5|(ľxI,(?o,FnQ')
Korektnost: algoritmus je správný a konečný.
IB102 Automaty, gramatiky a složitost, 3.10.2016
4/32
Příklad
IB102 Automaty, gramatiky a složitost, 3.10.2016
Eliminace ekvivalentních stavů
Nechť M = (0,51,5, q0l F) je DFA bez nedosažitelných stavů, jehož přechodová funkce je totální.
Definice 2.32. Stavy p, q nazveme jazykově ekvivalentní, psáno p pokud
p = q Mw G Z* : (<5(p, w) e F <5(g, w) e F).
IB102 Automaty, gramatiky a složitost, 3.10.2016
p = q <=^> Vi/i/ g 51* : (5(p, w) e F <=^>       w) e F)
Definice 2.34. Reduktem automatu M = (Q, Z, 5, g0> ^) nazveme konečný automat M/= = (Q/=, Z, 7y, [g0], F/=), kde
■ stavy jsou třídy rozkladu Q/= (třída obsahující stav q je [q]),
■ přechodová funkce rj je funkce splňující
Vp, q g Q, Va g Z : S(q, a) = p        ^(foM) = [p],
■ počáteční stav je třída rozkladu Q/= obsahující stav q0,
m koncové stavy jsou právě ty třídy rozkladu Q/=, které obsahují alespoň jeden koncový stav.
Věta 2.37. Nechť M = (Q, Z, 5, g0> F) je DFA bez nedosažitelných stavů s totální přechodovou funkcí. Pak L(M) = L(M/=).
IB102 Automaty, gramatiky a složitost, 3.10.2016
7/32
Algoritmus konstrukce minimálního automatu
Definice 2.38. Pro každé / e N0 definujeme binární relaci =/ na Q předpisem
p =j q Vtv e 51* : (\w\ < i =4> (8(p, w) e F       8(q, w) e F))
m p=j q  -<=>-  paq nelze „rozlišit" žádným slovem délky < /
■ p = q p =i q pro každé / e N0, tedy = = f]°l0 =,•
■ 1- =o  = {(p,q) I pe F 4=> qe F}
2. =/+1 = {(p, g) | p =ř- qr a Va e E : S(p, a) =,- 5(q, a)}
IB102 Automaty, gramatiky a složitost, 3.10.2016
8/32
Algoritmus konstrukce minimálního automatu
Vstup:   Deterministický konečný automat M = (Q, Z, S, qQ, F)
bez nedosažitelných stavů a s totální přechodovou funkcí. Výstu p: Red u kt M/=.
1
2
3
4
5
6
7
8
/ :=0
=o :={(p,q) \pe F <=> qeF} repeat
=/+i := {(p,q) | p =i q a Vael: S(p,á) =■, 8{q,á)}
/ := / + 1
until =/ = =/_1
Korektnost algoritmu: důkaz vynechán.
IB102 Automaty, gramatiky a složitost, 3.10.2016
9/32
Intuice
IB102 Automaty, gramatiky a složitost, 3.10.2016
10/32
Příklad
M	a	b	Ať	a		=0	a	b
1	2	—	->• 1	2	N	I 1	I	I
2	3	4	2	3	4	2	II	I
<- 3	6	5	<- 3	6	5	4	II	I
4	3	2	4	3	2	N	I	I
<- 5	6	3	<- 5	6	3	II 3	II	II
<r- 6	2	—	<- 6	2	N	5	II	II
7	6	1	N	/V	N	6	I	I
IB102 Automaty, gramatiky a složitost, 3.10.2016
11/32
Příklad
=1	a	b	=2	a	b			
I 1	II	I	I 1	III	II	M/=	a	b
N	I	I	II N	II	II	I	III	II
II 2	III	II	III 2	IV	III	II	II	II
4	III	II	4	IV	III	III	IV	III
III 3	IV	III	IV 3	V	IV	<r- IV	V	IV
5	IV	III	5	V	IV	<r- V	III	II
IV 6	II	I	V 6	III	II			
IB102 Automaty, gramatiky a složitost, 3.10.2016
12/32
Kanonický tvar konečných automatu
Motivace
	Mi	a	c	b
	1	IV	III	1
->•	II	V	III	III
<í—	III	II	1	1
<í—	IV	V	1	II
	V	II	V	V
IB102 Automaty, gramatiky a složitost, 3.10.2016
M2	a	b	c
I	III	V	V
II	IV	II	V
III	I	III	III
<r- IV	III	I	II
<- V	I	II	II
13/32
Kanonický tvar konečných automatu
	a	c	b		a	b	c
1	IV	III	1	A			
->• II	V	III	III	B			
<- III	II	1	1	C			
<- IV	V	1	II	D			
v	II	V	V	E			
IB102 Automaty, gramatiky a složitost, 3.10.2016
14/32
Rozšíření konečných automatů I Nedeterministické konečné automaty
IB102 Automaty, gramatiky a složitost, 3.10.2016
15/32
Definice 2.42. Nedeterministický konečný automat (NFA) je
M = (Q, Z, S, q0, F), kde význam všech složek je stejný jako v definici DFA s výjimkou přechodové funkce S. Ta je definována jako (totální) zobrazení í:QxI-^ 2°.
Rozšířená přechodová funkce 5 : Q x Z* -» 2°:
■ 5(q,£) = {q}
■ 5(Q3irva) = Up€Ä(Q,W)*(Aa)
Jazyk přijímaný nedeterministickým konečným automatem .M definujeme
L(.M) = {w g Z* | 5(qb, w)nF^ 0}.
IB102 Automaty, gramatiky a složitost, 3.10.2016
16/32
Příklad
IB102 Automaty, gramatiky a složitost, 3.10.2016
17/32
Ekvivalence DFA a NFA
Věta 2.43. Pro každý NFA M = (Q, Z, S, q0, F) existuje ekvivalentní deterministický konečný automat.
Důkaz. Definujeme DFA M! = (C, Z, č', {q0}, F') ■ Qf = 2°, tj. stavy automatu Mř jsou všechny podmnožiny Q.
■ Množina koncových stavů F' je tvořena právě těmi podmnožinami Q5 které obsahují nějaký prvek množiny F.
IB102 Automaty, gramatiky a složitost, 3.10.2016
18/32
Korektnost
■ M' je deterministický konečný automat.
m M a Mf jsou ekvivalentní: indukcí k délce i^gF dokážeme S(q0, w) = ^({go}, w)
Základní krok \ w\ = 0: Platí S(q0,e) = {q0} = Sř({q0},e). Indukční krok: Nechť w = va, pak
6(qo, va) = Upes(q0,v) <*(A a) = v), a) (viz definice 8')
= ô'(5'({q0}, v), a) (indukční předpoklad) = ^({go}, va).
Pak L(M) = L(A4')> neboť
w e L(M) 8{q0,w) n F 7^ 0 <^>
%o},^)nF/í 5;({qbh    e F iv g L(Mř). □
IB102 Automaty, gramatiky a složitost, 3.10.2016
19/32
Algoritmus transformace NFA na ekvivalentní DFA
Vstup:   Nedeterministický konečný automat M = (Q, Z, S, q0, F). Výstup: Ekvivalentní DFA M' = (<7, T, ô', {q0}, F)
bez nedosažitelných stavů a s totální přechodovou funkcí.
1: Q := {{Qo}}; S' := 0; F' := 0; Done := 0;
2: while {Q \ Done) ^ 0 do 3:     M := libovolný prvek množiny Q1 \ Done 4:     If M n F ^ 0 then F' ■= F' u {M} end if 5:     for all a e I! do
6: N :={JpeMS(p,á)
7: Q' := Q' U {N}
8: 5' := S' U {((M, a), A/)}
9:     end for
10:     Done := Done u {M}
11: end while
12: M' := (C, Z, *',{<*>}, F)
IB102 Automaty, gramatiky a složitost, 3.10.2016
20/32
Důsledky determinizace konečných automatů
Věta 2.44. Pro každé n e N existuje N FA o n stavech takový, že ekvivalentní DFA má i po minimalizaci 2n stavů.
Důkaz, vynechán.
b
b
IB102 Automaty, gramatiky a složitost, 3.10.2016 21/32
Rozšíření konečných automatů II Automaty s c-kroky
IB102 Automaty, gramatiky a složitost, 3.10.2016
22/32
Definice 2.46. Nedeterministický konečný automat s e-kroky je
M = (Q, Z, ô, q0, F), kde význam všech složek je stejný jako v definici N FA s výjimkou přechodové funkce 6. Ta je definována jako totální zobrazení ô : Q x (E u {e}) ->• 2°.
Rozšířená přechodová funkce
Definujeme funkci D£: Q -s- 2° následujícím předpisem. D£(p) je nejmenší množina X c Q taková, že platí:
■ p e X,
■ pokud q g X a r e 5(q, e), pak také r g X. Rozšíření funkce De na množiny stavů: pro V c Q položíme
D£(Y)= (J D£(q).
qeY
IB102 Automaty, gramatiky a složitost, 3.10.2016
23/32
Příklad - výpočet Dt
IB102 Automaty, gramatiky a složitost, 3.10.2016
24/32
Definice rozšířené přechodové funkce S : Q x I* -> 2°
■ 5(g,e) = De(qf),
■ wa) = Up£5(c7)w) Oe(í(p, a)).
Lemma 2.47. V přechodovém grafu automatu M existuje cesta
p-i A ... A pm 4- Qi 4 ... 4 c/n, kde m,n>1,ael, právě když qv, g %>i,a).
Jazyk přijímaný automatem .M s e-kroky definujeme
L(M) = {w e Z* | 5(qo, w)nF^ 0}.
IB102 Automaty, gramatiky a složitost, 3.10.2016
Příklad - výpočet rozšířené přechodové funkce
pro automat s e-kroky
IB102 Automaty, gramatiky a složitost, 3.10.2016
26/32
Ekvivalence automatů s e-kroky a NFA
Věta 2.48. Ke každému NFA M = (Q, 51,8, q0, F) s č-kroky existuje ekvivalentní NFA (bez č-kroků).
Důkaz. Konstrukce M = (Q, Z, 7, g0> G) bez č-kroků:
a) =     a) pro každé q g Q, a g Z
G= í F pokud D£(q0) n F = 0
\ Fu{q0} jinak
Korektnost: Dokážeme, že pro libovolné p g Q, 1/1/ g Z+ platí
(5(p51/1/) = ^(p51/1/) (indukcí vzhledem k délce slova w).
Algoritmus:
IB102 Automaty, gramatiky a složitost, 3.10.2016
Uzáverové vlastnosti regulárních jazyků
Věta 2.49. a 2.51. Třída regulárních jazyků je uzavřená na sjednocení, průnik, rozdíl a komplement.
Důkaz, synchronní paralelní kompozice automatů + komplement. □
Příklad. U   =   {a1 b1'd | 2/ > j > 0}
L2   =   {a}*.{b}* L3   =   {anbn | n > 0}
/.1 n /_2 = /-s
Jazyk /_2 je regulární, L3 není regulární =4> L1 není regulární.
IB102 Automaty, gramatiky a složitost, 3.10.2016
28/32
Věta 2.52. Třída regulárních jazyků je uzavřená na zřetězení. Důkaz.
Nechť L-i a L2 jsou regulární jazyky, rozpoznávané NFA
MA = (Qi, Z-i, 5-|, gi, F|) a M2 = (Cfe, E2,52, 92, F2), kde d n Q2 = 0.
Definujeme NFA s č-kroky M\ © A42 = (d u Q2, 511 u Z2,5, g-i, F2), kde
(J = 5i U(52u{((p^),{Q2}) |pe F|}.
IB102 Automaty, gramatiky a složitost, 3.10.2016
29/32
Korektnost: Chceme dokázat L(M^ © M2) = L(M^).L{M2)
d: Nechť u e L{M\), tedy 3r e F| splňující r e fr\(q-\,u). Nechť v e L{M2), tedy 52(q2, v) n F2   0. Pak
č(<7i,t;v) =    |J č(p,i0 d £(r,v) d S(qz,v) = 52(q2lv).
p€$(quii)
Protože S2(q2, i/)nF2/ 0, takSfa,uv) n F2 ^ 0. Tedy ívi/ g /-(.Mi © M2).
IB102 Automaty, gramatiky a složitost, 3.10.2016
□
30/32
Věta 2.53. Třída regulárních jazyků je uzavřená na iteraci. Důkaz.
Nechť L je regulární jazyk akceptovaný NFA M = (Q, Z, 5, g0j F). Definujeme NFA s č-kroky M* = (Qu {p}, Z, 5', p, {p}), kde p^Qí
ť = í u {((p, e), {Qo})} u {((q, e), {p}) | q e F}.
IB102 Automaty, gramatiky a složitost, 3.10.2016
Uzáverové vlastnosti regulárních jazyků - Shrnutí
IB102 Automaty, gramatiky a složitost, 3.10.2016
32/32