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ů).
IB102 Automaty a gramatiky, 8.10.2018 1/21
Konstrukce minimálního konečného automatu
Definice 2.18. Nechť M = (Q, 51, S, q0l F) je D FA. Stav q e Q nazveme dosažitelný, pokud existuje i^/Gľ takové, že S(q0l w) = q. Stav je nedosažitelný, pokud není dosažitelný.
IB102 Automaty a gramatiky, 8.10.2018
2/21
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 a gramatiky, 8.10.2018
4/21
Příklad
IB102 Automaty a gramatiky, 8.10.2018
Eliminace ekvivalentních stavů
Nechť M = (Q, Z, 5, Qo> 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 = g, pokud
p = q <=^> Vi/i/ g Z* : (5(p, í/i/) g F <=^> 5(q, w) e F).
IB102 Automaty a gramatiky, 8.10.2018
6/21
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, g0j F) je DFA bez nedosažitelných stavů s totální přechodovou funkcí. Pak L(M) = L(M/=).
IB102 Automaty a gramatiky, 8.10.2018
7/21
Algoritmus konstrukce minimálního automatu
Definice 2.38. Pro každé / g N0 definujeme binární relaci =, na Q předpisem
p =i q <=^> \/w g 51* : (\w\ < i =4> (5(p, w) g F <=^>       w) g F))
■ p=i q   <=^>   p a q nelze „rozlišit" žádným slovem délky < /
■ p = q p =,■ q pro každé / g N0, tedy = = f|/So =/'
■ 1. =o   = {(p, Q) | p g F ^ Q g F}
2. =/+1 = {(p, g) I p =/ q a Va g Z : í(p, a)    í(qr, a)}
IB102 Automaty a gramatiky, 8.10.2018
8/21
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 a gramatiky, 8.10.2018
9/21
Intuice
IB102 Automaty a gramatiky, 8.10.2018
10/21
Příklad
M	ď	b	M'	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	—	f- 6	2	N	5	II	II
7	6	1	N	/V	N	6	I	I
IB102 Automaty a gramatiky, 8.10.2018
11/21
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 a gramatiky, 8.10.2018
12/21
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 a gramatiky, 8.10.2018
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/21
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 a gramatiky, 8.10.2018
14/21
Rozšíření konečných automatů I Nedeterministické konečné automaty
IB102 Automaty a gramatiky, 8.10.2018
15/21
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(Q3iva) = 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 a gramatiky, 8.10.2018
16/21
Příklad
IB102 Automaty a gramatiky, 8.10.2018
17/21
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, Sř, {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 a gramatiky, 8.10.2018
18/21
Korektnost
M' je deterministický konečný automat. MaM' jsou ekvivalentní:
indukcí k délce i^gF dokážeme S(q0, w) = Sf({q0}, w) Základní krok \ w\ =0: Platí 5(q0, e) = {g0} = S'({q0}, e). Indukční krok: Nechť w = va, pak
5(qo, va) = Up^c^)SÍP> a) = ^í**    a) (viz definice ^)
= ^(^({Qo}, v)> a) (indukční předpoklad) = S'({q0}, va).
Pak L(M) = Z-(A4')> neboť
w e L(M) S(q0,w)nF^®
W^jnF / 0 ^ ^'({Qb},    e F ^ w e L(M'). □
IB102 Automaty a gramatiky, 8.10.2018
19/21
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 a gramatiky, 8.10.2018
20/21
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 a gramatiky, 8.10.2018 21/21