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, 12.10.2015
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, 12.10.2015
2/32
Příklad
IB102 Automaty, gramatiky a složitost, 12.10.2015
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 : <5(p, a) = <7}
5:      / := /' + 1 6: until S, = 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, 12.10.2015
4/32
Příklad
IB102 Automaty, gramatiky a složitost, 12.10.2015
5/32
Eliminace ekvivalentních stavů
Nechť M = (Q, 51, S, 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(q, w) e F).
IB102 Automaty, gramatiky a složitost, 12.10.2015
p = q <=^> Mw g 51* : (5(p, 1/1/) g F <=^>        w) g F)
Definice 2.34. Reduktem automatu M = (Q, 51,5, g0> F) nazveme konečný automat M/= = (Q/=, 51,7/, [g0], F/=), kde
■ stavy jsou třídy rozkladu Q/= (třída obsahující stav q je [q]),
■ přechodová funkce 77 je funkce splňující
Vp,q g Q,Vae Z : ô(q,a) = p        rjQg], 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, ô, q0, 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, 12.10.2015
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 =i q Vw e Z* : (| w| < / =4> (8(p, w) e F       8(q, w) e F))
m p=, q   -<=>-   paq nelze „rozlišit" žádným slovem délky < /
■ p = q p =j q pro každé / e N0, tedy = = f]°l0 =t
■ 1-=o  = {(P,q) I pe F <=^ qe F}
2. =/+1 = {(p, q) | p =,- q a Va € Z : 5(p, a) =, a)}
IB102 Automaty, gramatiky a složitost, 12.10.2015
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) =,■ <S(g,a)}
/ := / + 1
until =, = =/_i
Korektnost algoritmu: důkaz vynechán.
IB102 Automaty, gramatiky a složitost, 12.10.2015
9/32
Intuice
IB102 Automaty, gramatiky a složitost, 12.10.2015
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, 12.10.2015
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, 12.10.2015
12/32
Kanonický tvar konečných automatu
	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, 12.10.2015
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, 12.10.2015
14/32
Rozšíření konečných automatů I Nedeterministické konečné automaty
IB102 Automaty, gramatiky a složitost, 12.10.2015
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(g,e) = {g}
■ 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, 12.10.2015
16/32
Příklad
IB102 Automaty, gramatiky a složitost, 12.10.2015
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}, F')
■ Qf = 2°, tj. stavy automatu ./Vť 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, 12.10.2015
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) = S'({q0}, w) Základní krok \ w\ =0: Platí S(q0, e) = {q0} = S'({q0}, e). Indukční krok: Nechť w = va, pak
5(cto, va) = UpGÄíqb^) <*(Aa) = v), a) (viz definice 8')
= v), a) (indukční předpoklad) = č'({go}, va)
Pak L(A4) = L(M'), neboť
iy e L(M)        5(g0, w) n F ^ 0
%0}^)nF/ 0 8'({q0},w) e F' w e L(Mf). □
IB102 Automaty, gramatiky a složitost, 12.10.2015
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 (7 \ Done 4:     If M n F ŕ 0 then F' := F u {/W} end if 5:     for all a e I! do
6: N := \JpeM S(p, ä)
7: Q' := Q' U {N}
8: 5':= 5'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, 12.10.2015
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, 12.10.2015
21/32
Rozšíření konečných automatů II Automaty s c-kroky
IB102 Automaty, gramatiky a složitost, 12.10.2015
22/32
Definice 2.46. Nedeterministický konečný automat s e-kroky je
M = (Q, Z, S, q0l F), kde význam všech složek je stejný jako v definici N FA s výjimkou přechodové funkce S. Ta je definována jako totální zobrazení í:Ox(Iu {e}) -> 2°.
Rozšířená přechodová funkce
Definujeme funkci D£ : Q -> 2° následujícím předpisem. D£(p) je nejmenší množina X c Q taková, že platí:
■ peX,
■ pokud q e X a r e 8{q, s), pak také r g X. Rozšíření funkce D£ na množiny stavů: pro Y c Q položíme
IB102 Automaty, gramatiky a složitost, 12.10.2015
23/32
Příklad - výpočet Dt
IB102 Automaty, gramatiky a složitost, 12.10.2015
24/32
Definice rozšířené přechodové funkce 5 : Q x E* -> 2°
■ 5(c/,e) = De(Q),
■ 5(qr, wa) = Upeá(a,W) Oe(<J(p, a)).
Lemma 2.47. V přechodovém grafu automatu M existuje cesta Pí A ... A pm A Qi A ... A qfn, kde m, n > 1, a g E, právě když
Qn g %>i,a).
Jazyk přijímaný automatem .M s e-kroky definujeme
L(M) = {w e E* | 5(<7o, w) n F ^ 0}.
IB102 Automaty, gramatiky a složitost, 12.10.2015
Příklad - výpočet rozšířené přechodové funkce
pro automat s e-kroky
IB102 Automaty, gramatiky a složitost, 12.10.2015
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, 51,7, Qo> 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 e Q, 1/1/ e Z+ platí
(5(p5 w) = <y(p?    (indukcí vzhledem k délce slova w).
Algoritmus:
IB102 Automaty, gramatiky a složitost, 12.10.2015
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. lá   =   {äti d | 2/ > j > 0}
l2 = {ay.{by
l3   =   {anbn | n > 0} L1 n /_2 = l3
Jazyk L2 je regulární, Z_3 není regulární =^>     není regulární.
IB102 Automaty, gramatiky a složitost, 12.10.2015
28/32
Věta 2.52. Třída regulárních jazyků je uzavřená na zřetězení. Důkaz.
Nechť L| a L2 jsou regulární jazyky, rozpoznávané NFA
MA = (d, Z1, ^, q1 , ^) a >í2 = (Cfe, E2, <fe,02, F2), kde d n q2 = 0.
Definujeme NFA s č-kroky M\ © .M2 = (d u Q2, 511 u Z2,5, g-i, F2), kde
(J = 5i u(52u{((p^),{Q2}) |pe Fi}.
IB102 Automaty, gramatiky a složitost, 12.10.2015
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 l/v g L(A^i © A^)-
IB102 Automaty, gramatiky a složitost, 12.10.2015
□
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, g0, F). Definujeme NFA s č-kroky M* = (Qu {p},z,5',p,{p}), kde p ^ Qí
ť = í U {((p, e), {Qo})} u {((Q, e), {p}) | Q g F}.
IB102 Automaty, gramatiky a složitost, 12.10.2015
Uzáverové vlastnosti regulárních jazyků - Shrnutí
IB102 Automaty, gramatiky a složitost, 12.10.2015
32/32