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 Myhill-Nerodovy věty. □
IB102 Automaty, gramatiky a složitost, 29.9.2014
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, 29.9.2014
2/32
Příklad
IB102 Automaty, gramatiky a složitost, 29.9.2014
3/32
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 := Sj u {q I 3p e Si, a e Z : S(p, ä) = q}
5:      / := /' + 1 6: until Si = S/_i 7: Q' := S/
8: M' :=(0',I)5|ffxZ,(/o,FnQ')
Korektnost: algoritmus je správný a konečný.
IB102 Automaty, gramatiky a složitost, 29.9.2014
4/32
Příklad
IB102 Automaty, gramatiky a složitost, 29.9.2014
5/32
Eliminace ekvivalentních stavů
Nechť M = (Q, Z, 5, g0, 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        \/w g Z* : (<5(p, w) e F        <5(<7, w) g F).
IB102 Automaty, gramatiky a složitost, 29.9.2014
p = q <=^> Mw g 51* : (5(p, w) e F <=^> 5(qr, w) g F)
Definice 2.34. Reduktem automatu M = (Q, 51,5, <70, F) nazveme konečný automat M/= = (Q/=, 51,7/, [qr0], F/=), kde
■ stavy jsou třídy rozkladu Q/= (třída obsahující stav g je [q]),
■ přechodová funkce 77 je funkce splňující
Vp, Q g Q, Va g Z : 5(qr, a) = p        ^([Q],a) = [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, 51,5, <70, 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, 29.9.2014
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    q Vw e 51* : (| w| < / =4> (<5(p, w) e F       8(q, w) e F))
m p=, q  -<=>-   paq nelze „rozlišit" žádným slovem délky < /
■ p = q p =,■ q pro každé / e N0, tedy = = f]°l0 =■,
■ 1-=o  = {(p,q)\pe F ^ qe F}
2. =;+1 = {(p, g) | p =i,q a Vael: 5(p, a) =, a)}
IB102 Automaty, gramatiky a složitost, 29.9.2014
8/32
Algoritmus konstrukce minimálního automatu
Vstup:   Deterministický konečný automat M = (O, Z, S, q0, F)
bez nedosažitelných stavů a s totální přechodovou funkcí. Výstup: ReóuWXM/=.
1
2
3
4
5
6
7
8
/ :=0
=o := {(p,q) \ P^F ^ qeF} repeat
=/+i := {(p,q)\p=,q A Vael: <S(p,a) =,■ 5(q,a)}
/ := / + 1
until =, = =/_i
Korektnost algoritmu: důkaz vynechán.
IB102 Automaty, gramatiky a složitost, 29.9.2014
9/32
Intuice
IB102 Automaty, gramatiky a složitost, 29.9.2014
10/32
Příklad
M	ď	b	Ať	a	Ď	=0	ď	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, gramatiky a složitost, 29.9.2014
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, 29.9.2014
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, 29.9.2014
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, 29.9.2014
14/32
Rozšíření konečných automatů I Nedeterministické konečné automaty
IB102 Automaty, gramatiky a složitost, 29.9.2014
15/32
Definice 2.42. Nedeterministický konečný automat (NFA) je
M = (Q, Z, 5, cfo, 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í í:QxZ-^ 2°.
Rozšířená přechodová funkce 5 : Q x Z* -» 2°:
■ 5(qr,e) = {qr}
■ 5(Q,iva) = Up€Ä(Q,W)*(Aa)
Jazyk přijímaný nedeterministickým konečným automatem .M definujeme
L(.M) = {w g Z* | 5(qb, w) n F ^ 0}.
IB102 Automaty, gramatiky a složitost, 29.9.2014
16/32
Příklad
IB102 Automaty, gramatiky a složitost, 29.9.2014
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, 5', {q0}, F1)
■ Qf = 2°, tj. stavy automatu Mf jsou všechny podmnožiny Q.
■ ^(P,a) = UaGP^a)-
■ 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, 29.9.2014
18/32
Korektnost
Mf je deterministický konečný automat. M a M! jsou ekvivalentní:
indukcí k délce i^gF dokážeme S(q0, w) = č'({<70}, w) Základní krok \ w\ =0: Platí S(q0, e) = {q0} = S'({q0}, e). Indukční krok: Nechť w = va, pak
5(cfo, va) = UpGá(Qo^)     a) = a) (viz definice í')
= č'(£'({<%}, v), a) (indukční předpoklad) = č'({<7o}, va)
Pak L(A4) = L(M'), neboť iveL(M) 5(go,^)nF^0
6'({qo},w)nFr 0 <S'({gb},    e F w e /-(A^O- □
IB102 Automaty, gramatiky a složitost, 29.9.2014
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 (Cy \ Done) ^ 0 do 3:     M := libovolný prvek množiny (7 \ 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 {A/}
8: 5' :=S'u{{(M,ä),N)}
9:     end for
10:     Done := Done u {M} 11: end while
12: Ať :=(Q',Z,y,{£7o},F)
IB102 Automaty, gramatiky a složitost, 29.9.2014
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.
IB102 Automaty, gramatiky a složitost, 29.9.2014
21/32
Rozšíření konečných automatů II Automaty s c-kroky
IB102 Automaty, gramatiky a složitost, 29.9.2014
22/32
Definice 2.46. Nedeterministický konečný automat s e-kroky je
M = (Q, Z, S, Qo, 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£: O -s- 2° následujícím předpisem. D£(p) je nejmenší množina X c Q taková, že platí:
■ p e X,
m pokud q g X a r e <5(g, e), pak také r e X. Rozšíření funkce D£ na množiny stavů: pro V c Q položíme
D£(Y)= \jD£(q).
qeY
IB102 Automaty, gramatiky a složitost, 29.9.2014
23/32
Příklad - výpočet Dt
IB102 Automaty, gramatiky a složitost, 29.9.2014
24/32
Definice rozšířené přechodové funkce 5 : Q x E* -> 2°
■ %£) = D£(c/)!
■ 5(qr, wa) = Upeá(a,W) 0£((5(p, a)).
Lemma 2.47. V přechodovém grafu automatu M existuje cesta Pí A ... A pm A g-i A ... A gn, kde m, n > 1, a g Z, právě když qn e 5{pi, a).
Jazyk přijímaný automatem M s e-kroky definujeme
L(M) = {w e Z* |       w) n F ^ 0}.
IB102 Automaty, gramatiky a složitost, 29.9.2014
Příklad - výpočet rozšířené přechodové funkce
pro automat s e-kroky
IB102 Automaty, gramatiky a složitost, 29.9.2014
26/32
Ekvivalence automatů s e-kroky a NFA
Věta 2.48. Ke každému NFA M = (Q, Z, 5, cfo, F) s č-kroky existuje ekvivalentní NFA (bez č-kroků).
Důkaz. Konstrukce .M = (Q, Z, 7, cfo, G) bez č-kroků:
a) = 5(qr, a) pro každé g g Q, a g Z
G= í F pokud D£(q0) n F = 0
\ Fu{g0} jinak
Korektnost: Dokážeme, že pro libovolné p e Q, w e Z+ platí
5(p? w) = ^(p5    (indukcí vzhledem k délce slova w).
Algoritmus:
IB102 Automaty, gramatiky a složitost, 29.9.2014
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. ^   =   {attid | 2/ > j > 0}
L2   = {a}*.{b}* L3   =   {anbn | n > 0}
Z-1 n /_2 = L3
Jazyk /_2 je regulární, Z_3 není regulární =^ L-i není regulární.
IB102 Automaty, gramatiky a složitost, 29.9.2014
28/32
Věta 2.52. Třída regulárních jazyků je uzavřená na zřetězení. Důkaz.
Nechť Li a L2 jsou regulární jazyky, rozpoznávané NFA
MA = (C3i, Zi, (Ji,   , F,) a A<2 = (Q>, ^2,<fe, <fe, F2), kde d n Q2 = 0.
Definujeme NFA s č-kroky M\ © Mz = (d u Q2, 511 u Z2,5, Qi, F2), kde
5 = (Ji u (J2 u {((p, e), {g2}) | p e F,}.
IB102 Automaty, gramatiky a složitost, 29.9.2014
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, i/)nF2/ 0. Pak
p€5(quu)
Protože S2(q2, v)nF2^ 0, tak Sfa, uv) n F2 ^ 0. Tedy ívv g /-(.Mi © A^)-
IB102 Automaty, gramatiky a složitost, 29.9.2014
□
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, q0, F).
Definujeme NFA s č-kroky M* = (Qu {p}, Z,5',p, {p}), kde p 0 Q c
ť = í u {((p, e), {g0})} u {((g, e), {p}) | g g F}.
IB102 Automaty, gramatiky a složitost, 29.9.2014
Uzáverové vlastnosti regulárních jazyků - Shrnutí
IB102 Automaty, gramatiky a složitost, 29.9.2014
32/32