Formální jazyky a automaty
Konzervativní rozšíření konečných automatů:
Nedeterminismus a ε-kroky
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
Aplikace: Hledání výskytu slova v textu
DFA pro Σ∗
nano:
2 / 13
Aplikace: Hledání výskytu slova v textu
DFA pro Σ∗
nano:
2 / 13
Aplikace: Hledání výskytu slova v textu
DFA pro Σ∗
nano:
NFA:
2 / 13
Aplikace: Hledání výskytu slova v textu
DFA pro Σ∗
nano:
NFA:
2 / 13
Nedeterministický konečný automat (NFA)
Definice 2.42. (NFA)
Nedeterministický konečný automat (NFA) je M = (Q, Σ, δ, q0, F),
kde význam všech složek je stejný jako v definici DFA s výjimkou
přechodové funkce δ. Ta je definována jako (totální) zobrazení
δ : Q × Σ → 2Q
.
3 / 13
Nedeterministický konečný automat (NFA)
Definice 2.42. (NFA)
Nedeterministický konečný automat (NFA) je M = (Q, Σ, δ, q0, F),
kde význam všech složek je stejný jako v definici DFA s výjimkou
přechodové funkce δ. Ta je definována jako (totální) zobrazení
δ : Q × Σ → 2Q
.
Rozšířená přechodová funkce ˆδ : Q × Σ∗
→ 2Q
:
ˆδ(q, ε) = {q}
ˆδ(q, wa) = p∈ˆδ(q,w) δ(p, a)
Jazyk přijímaný nedeterministickým konečným automatem M:
L(M) = {w ∈ Σ∗
| ˆδ(q0, w) ∩ F ̸= ∅}.
3 / 13
Ekvivalence DFA a NFA: Determinizace
Věta 2.43.
Pro každý NFA M = (Q, Σ, δ, q0, F) existuje ekvivalentní
deterministický konečný automat.
Důkaz Definujeme DFA M′
= (Q, Σ, ∆, {q0}, F)
Q = 2Q
, tj. stavy automatu M′
jsou všechny podmnožiny Q.
∆(P, a) = q∈P δ(q, a).
Množina koncových stavů F je tvořena právě těmi podmnožinami
Q, které obsahují nějaký prvek množiny F.
4 / 13
Determinizace: Příklad
Q = 2Q
∆(P, a) = q∈P δ(q, a).
F = {P | P ∩ F ̸= ∅}
5 / 13
Determinizace: Korektnost
M′
je deterministický konečný automat.
M a M′
jsou ekvivalentní:
indukcí k délce w ∈ Σ∗
dokážeme ˆδ(q0, w) = ∆({q0}, w)
Základní krok |w| = 0: Platí ˆδ(q0, ε) = {q0} = ∆({q0}, ε).
Indukční krok: Nechť w = va, pak
ˆδ(q0, va) =
p∈ˆδ(q0,v)
δ(p, a) (viz definici ˆ pro NFA)
= ∆(ˆδ(q0, v), a) (viz definici ∆)
= ∆(∆({q0}, v), a) (indukční předpoklad)
= ∆({q0}, va) (viz definici ˆ pro DFA)
Pak L(M) = L(M′
), neboť
w ∈ L(M) ⇐⇒ ˆδ(q0, w) ∩ F ̸= ∅ ⇐⇒ ∆({q0}, w) ∩ F ̸= ∅
⇐⇒ ∆({q0}, w) ∈ F ⇐⇒ w ∈ L(M′
).
6 / 13
Algoritmus transformace NFA na ekvivalentní DFA
Vstup: Nedeterministický konečný automat M = (Q, Σ, δ, q0, F).
Výstup: Ekvivalentní DFA M′
= (Q, Σ, ∆, {q0}, F)
bez nedosažitelných stavů a s totální přechodovou funkcí.
1: Q := ∅; ∆ := ∅; F := ∅;
2: Todo := {{q0}};
3: while Todo ̸= ∅ do
4: odstraň libovolný P z Todo
5: přidej P do Q
6: if P ∩ F ̸= ∅ then přidej P do F end if
7: for all a ∈ Σ do
8: Pa := p∈P δ(p, a)
9: přidej ((P, a), Pa) do ∆
10: if Pa /∈ Q then přidej Pa do Todo
11: return M′
:= (Q, Σ, ∆, {q0}, F)
7 / 13
Aplikace: Knuth-Morris-Pratt
8 / 13
Velikosti NFA a DFA
Věta 2.44.
Pro každé n ∈ N existuje NFA o n stavech takový, že ekvivalentní
DFA má i po minimalizaci 2n
stavů.
Důkaz zde s jiným automatem: n-té písmeno od konce je a
9 / 13
Automaty s εεε-kroky
Definice 2.46.
Nedeterministický konečný automat s ε-kroky je M = (Q, Σ, δ, q0, F),
kde význam všech složek je stejný jako v definici NFA s výjimkou
přechodové funkce δ. Ta je definována jako totální zobrazení
δ : Q × (Σ ∪ {ε}) → 2Q
.
Příklad pro 0∗
1∗
2∗
:
10 / 13
Automaty s εεε-kroky
Definice 2.46.
Nedeterministický konečný automat s ε-kroky je M = (Q, Σ, δ, q0, F),
kde význam všech složek je stejný jako v definici NFA s výjimkou
přechodové funkce δ. Ta je definována jako totální zobrazení
δ : Q × (Σ ∪ {ε}) → 2Q
.
Příklad pro 0∗
1∗
2∗
:
Rozšířená přechodová funkce
Definujeme funkci Dε : Q → 2Q
následujícím předpisem.
Dε(p) je nejmenší množina X ⊆ Q taková, že platí:
p ∈ X,
pokud q ∈ X a r ∈ δ(q, ε), pak také r ∈ X.
Rozšíření funkce Dε na množiny stavů: pro Y ⊆ Q položíme
Dε(Y ) =
q∈Y
Dε(q).
10 / 13
Definice rozšířené přechodové funkce ˆδ : Q × Σ∗
→ 2Q
ˆδ(q, ε) = Dε(q),
ˆδ(q, wa) = p∈ˆδ(q,w) Dε(δ(p, a)).
Lemma 2.47. V přechodovém grafu automatu M existuje cesta
p1
ε
→ . . .
ε
→ pm
a
→ q1
ε
→ . . .
ε
→ qn, kde m, n ≥ 1, a ∈ Σ, právě když
qn ∈ ˆδ(p1, a).
Jazyk přijímaný automatem M s ε-kroky definujeme
L(M) = {w ∈ Σ∗
| ˆδ(q0, w) ∩ F ̸= ∅}.
11 / 13
Ekvivalence automatů s εεε-kroky a NFA
Věta 2.48. (Odstranění εεε-kroků)
Ke každému NFA M = (Q, Σ, δ, q0, F) s ε-kroky existuje ekvivalentní
NFA (bez ε-kroků).
12 / 13
Ekvivalence automatů s εεε-kroky a NFA
Věta 2.48. (Odstranění εεε-kroků)
Ke každému NFA M = (Q, Σ, δ, q0, F) s ε-kroky existuje ekvivalentní
NFA (bez ε-kroků).
12 / 13
Důkaz. Konstrukce M = (Q, Σ, γ, q0, G) bez ε-kroků:
γ(q, a) = ˆδ(q, a) pro každé q ∈ Q, a ∈ Σ
G =
F pokud Dε(q0) ∩ F = ∅
F ∪ {q0} jinak
Korektnost: Dokážeme, že pro libovolné p ∈ Q, w ∈ Σ+
platí
ˆδ(p, w) = ˆγ(p, w) (indukcí vzhledem k délce slova w).
13 / 13