Formální jazyky a automaty
Minimalizace, učení automatů
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
Minimální automat
Minimální DFA
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ů) a má | ∼L |
stavů.
Důkaz. MN + Lemma 2.27
2 / 15
Eliminace nedosažitelných stavů: Příklad
Definice 2.18.
Nechť M = (Q, Σ, δ, q0, F) je DFA. Stav q ∈ Q nazveme dosažitelný,
pokud existuje w ∈ Σ∗
takové, že ˆδ(q0, w) = q. Stav je nedosažitelný,
pokud není dosažitelný.
3 / 15
Algoritmus pro eliminaci nedosažitelných stavů DFA
Vstup: Deterministický konečný automat M = (Q, Σ, δ, q0, F).
Výstup: Ekvivalentní automat M′
bez nedosažitelných stavů.
1: i := 0
2: Si := {q0}
3: repeat
4: Si+1 := Si ∪ {q | ∃p ∈ Si , a ∈ Σ : δ(p, a) = q}
5: i := i + 1
6: until Si = Si−1
7: Q′
:= Si
8: M′
:= (Q′
, Σ, δ|Q′×Σ, q0, F ∩ Q′
)
4 / 15
Eliminace ekvivalentních stavů: Příklad
1
2 3 4
5 6
a
c
b
a
b
c a
b
a
a
a
5 / 15
Eliminace ekvivalentních stavů
Nechť M = (Q, Σ, δ, q0, 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 ≡ q, pokud
p ≡ q ⇐⇒ ∀w ∈ Σ∗
: (ˆδ(p, w) ∈ F ⇐⇒ ˆδ(q, w) ∈ F).
1
2 3 4
5 6
a
c
b
a
b
c a
b
a
a
a
6 / 15
p ≡ q ⇐⇒ ∀w ∈ Σ∗
: (ˆδ(p, w) ∈ F ⇐⇒ ˆδ(q, w) ∈ F)
Definice 2.34.
Reduktem automatu M = (Q, Σ, δ, q0, F) nazveme konečný automat
M/≡ = (Q/≡, Σ, η, [q0], F/≡), kde
stavy jsou třídy rozkladu Q/≡ (třída obsahující stav q je [q]),
přechodová funkce η je funkce splňující
∀p, q ∈ Q, ∀a ∈ Σ : δ(q, a) = p =⇒ η([q], a) = [p],
počáteční stav je třída rozkladu Q/≡ obsahující stav q0,
koncové stavy jsou právě ty třídy rozkladu Q/≡, které obsahují
alespoň jeden koncový stav.
7 / 15
p ≡ q ⇐⇒ ∀w ∈ Σ∗
: (ˆδ(p, w) ∈ F ⇐⇒ ˆδ(q, w) ∈ F)
Definice 2.34.
Reduktem automatu M = (Q, Σ, δ, q0, F) nazveme konečný automat
M/≡ = (Q/≡, Σ, η, [q0], F/≡), kde
stavy jsou třídy rozkladu Q/≡ (třída obsahující stav q je [q]),
přechodová funkce η je funkce splňující
∀p, q ∈ Q, ∀a ∈ Σ : δ(q, a) = p =⇒ η([q], a) = [p],
počáteční stav je třída rozkladu Q/≡ obsahující stav q0,
koncové stavy jsou právě ty třídy rozkladu Q/≡, které obsahují
alespoň jeden koncový stav.
Věta 2.37.
Nechť M = (Q, Σ, δ, q0, F) je DFA bez nedosažitelných stavů
s totální přechodovou funkcí. Pak L(M/≡) = L(M).
Důkaz. Indukcí ˆη([q0], u) = ˆη([q0], v) ⇐⇒ ˆδ(q0, u) ≡ ˆδ(q0, v).
7 / 15
Algoritmus konstrukce minimálního automatu
Definice 2.38.
Pro každé i ∈ N0 definujeme binární relaci ≡i na Q předpisem
p ≡i q ⇐⇒ ∀w ∈ Σ∗
: |w| ≤ i =⇒ (ˆδ(p, w) ∈ F ⇐⇒ ˆδ(q, w) ∈ F)
p ≡i q ⇐⇒ p a q nelze „rozlišit“ žádným slovem délky ≤ i
p ≡ q ⇐⇒ p ≡i q pro každé i ∈ N0, tedy ≡ =
∞
i=0 ≡i
1. ≡0 = {(p, q) | p ∈ F ⇐⇒ q ∈ F}
2. ≡i+1 = {(p, q) | p ≡i q ∧ ∀a ∈ Σ : δ(p, a) ≡i δ(q, a)}
8 / 15
Algoritmus konstrukce minimálního automatu
Vstup: Deterministický konečný automat M = (Q, Σ, δ, q0, F)
bez nedosažitelných stavů a s totální přechodovou funkcí.
Výstup: Redukt M/≡.
1: i := 0
2: ≡0 := {(p, q) | p ∈ F ⇐⇒ q ∈ F}
3: repeat
4: ≡i+1 := {(p, q) | p ≡i q ∧ ∀a ∈ Σ : δ(p, a) ≡i δ(q, a)}
5: i := i + 1
6: until ≡i = ≡i−1
7: ≡ := ≡i
8: M/≡ := (Q/≡, Σ, η, [q0], F/≡)
9 / 15
Minimalizace: Příklad
M a b
→ 1 2 −
2 3 4
← 3 6 5
4 3 2
← 5 6 3
← 6 2 −
7 6 1
M′
a b
→ 1 2 N
2 3 4
← 3 6 5
4 3 2
← 5 6 3
← 6 2 N
N N N
≡0 a b
I 1 I I
2 II I
4 II I
N I I
II 3 II II
5 II II
6 I I
10 / 15
Minimalizace: Příklad
≡1 a b
I 1 II I
N I I
II 2 III II
4 III II
III 3 IV III
5 IV III
IV 6 II I
≡2 a b
I 1 III II
II N II II
III 2 IV III
4 IV III
IV 3 V IV
5 V IV
V 6 III II
M/≡ a b
→ I III II
II II II
III IV III
← IV V IV
← V III II
11 / 15
Kanonický tvar konečných automatů: Motivace
M1 a c b
I IV III I
→ II V III III
← III II I I
← IV V I II
V II V V
M2 a b c
→ I III V V
II IV II V
III I III III
← IV III I II
← V I II II
12 / 15
Kanonický tvar konečných automatů: Příklad
a c b
I IV III I
→ II V III III
← III II I I
← IV V I II
V II V V
a b c
→ 1
2
3
4
5
13 / 15
* Automata learning
14 / 15
* Automata learning
14 / 15
* Angluin’s L* Algorithm for DFA Learning
15 / 15
* Angluin’s L* Algorithm for DFA Learning
15 / 15