AP9, IN9 Konečné automaty

definice, konstrukce konečného automatu, minimalizace konečného automatu, převod nedeterministického konečného automatu na deterministický automat

Abychom mohli definovat jazyk akceptovaný automatem, je třeba zavézt rozšířenou přechodovou funkci

: Q x //* //→ Q definována induktivně vzhledem k délce slova ze *:

• (q, ) = q pro každý stav q Q
• (q, wa) =
  • ((q, w), a) je-li (q, w) i ((q, w), a) definováno
  • jinak

Jazyk akceptovaný konečným automatem M, označovaný L(M) je tvořen právě všemi takovými slovy, pod kterými automat přejde z počátečního stavu do některého z koncových.
L(M) = {w * | (q₀,w) F}

: Q x //* //→ 2^Q, definována induktivně vzhledem k délce slova ze *:

• (q, ) = {q}
• (q, wa) =

Jazyk akceptovaný nedeterministickým konečným automatem M, označovaný L(M) je tvořen právě všemi takovými slovy, pod kterými automat přejde z počátečního stavu do některého z koncových.
L(M) = {w * | (q₀,w) F }

Mějme například jazyk L = {w {a, b}* | w obsahuje podslovo abaa}.

• konstrukce konečného automatu, který rozpoznává daný jazyk, je obecně netriviální úkol. Pro zjednodušení proto volíme označení stavů tak, aby bylo patrné, jaká část podslova abaa již byla automatem přečtena.

Konečný automat akceptující jazyk L je možné reprezentovat:

kde přechodová funkce vypadá následovně:

• není určen jednoznačně. Může se lišit podle toho, jakým způsobem jej konstruujeme.
• Příklad výpočetního stromu pro automat M:

Pro dané automaty M₁ a M₂ umožňuje sestrojit automat rozpoznávající průnik, sjednocení či rozdíl jazyků L(M₁) a L(M₂).
Nechť M₁ = (Q₁, , ₁, q₁, F₁), M₂ = (Q₂, , ₂, q₂, F₂) a přechodové funkce ₁, ₂ jsou totální.
Definujeme konečný automat M₃ = (Q₃, , ₃, q₃, F₃), kde

• Q₃ = Q₁ x Q₂ = {(p,q) | p Q₁, q Q₂}
• F₃ = F₁ x F₂ = {(p,q) | p F₁, q F₂}
• q₃ = (q₁, q₂)
• ₃( (p,q),a) = (₁(p,a),₂(q,a) )

Potom L(M₃) = L(M₁) L(M₂)

Podobně pro sjednocení a rozdíl - zmení sa len množina koncových stavov

• F₃ = (F₁ x Q₂) (Q₁ x F₂) = {(p,q) | p F₁ ∨ q F₂} pre zjednotenie
• F₃ = F₁ - F₂ = {(p,q) | p F₁ ∧ q F₂} pre rozdiel

K automatu M = (Q, , , q₀, F) s totální přechodovou funkcí sestrojíme automat rozpoznávající jazyk co–L(M) jako = (Q, , , q₀, Q – F).

Poznámka: přechodovou funkci ztotálníme tak, že přidáme nový nekoncový stav („černá díra“), do kterého „nasměrujeme chybějící šipky“.

Minimální konečný automat = automat s nejmenším počtem stavů, který rozpoznává daný regulární jazyk L.
Existence minimálního konečného automatu souvisí s Myhill–Nerodovou větou (viz otázka AP8,IN8 Regulární jazyky), kterou můžeme přeformulovat takto:

Minimalizace konečného automatu probíhá tak, že nejprve jsou odstraněny nedosažitelné stavy a poté jsou ztotožněny jazykově ekvivalentní stavy.

Vstup: Konečný automat M = (Q, , , q₀, F)
Výstup: Ekvivalentní automat M' bez nedosažitelných stavů.

Algoritmus

i := 0
S_i := {q₀}
repeat S_i+1 := S_i {q | p S_i, a : (p, a) = q}
i := i + 1
until S_i = S_i–1
Q' := S_i
M' = (Q', , |_Q', q₀, F Q')

Poznámka: Zápis |_Q' znamená, že funkce je omezena na množinu Q'.
Intuitivně: Množina S_i je množina stavů dosažitelná v automatu v maximálně i krocích.

Nechť M = (Q, , , q₀, F) je konečný automat bez nedosažitelných stavů, jehož přechodová funkce je totální.

Definice - jazykově ekvivalentní stavy

Stavy p, q nazveme jazykově ekvivalentní, psáno p ≡ q, pokud
p ≡ q w * : ((p, w) F (q, w) F).

Definice - Redukt

Reduktem automatu M = (Q, , , q₀, F) nazveme konečný automat M/_≡ = (Q/_≡, , , [q₀], 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 q₀.
• Koncové stavy jsou právě ty třídy rozkladu Q/_≡, které obsahují alespoň jeden koncový stav.

Věta

Nechť M = (Q, , , q₀, F) je konečný automat bez nedosažitelných stavů s totální přechodovou funkcí. Pak L(M) = L(M/_≡).

Definice

Pro každé i ₀ definujeme binární relaci ≡_i na Q předpisem
p ≡_i q w *.|w| i : ((p, w) F (q, w) F)

• p ≡_i q právě když p a q nelze „rozlišit“ žádným slovem délky i
• p ≡ q právě když p ≡_i q pro každé i ₀. (≡ = _i)

1. ≡₀ = {(p, q) | p F q F}
2. ≡_i+1 = {(p, q) | p ≡_i q a : (p, a) ≡_i (q, a)}

Vstup: Konečný automat M = (Q, , , q₀, F) bez nedosažitelných stavů s totální přechodovou funkcí
Výstup: Redukt M/_≡.

Algoritmus

i := 0
≡₀ := {(p, q) | p F q F}
repeat
≡_i+1 := {(p, q) | p ≡_i q a : (p, a) ≡_i (q, a)}
i := i + 1
until ≡_i = ≡_i–1
≡ = ≡_i
M/_≡ := (Q/_≡, , , [q₀], F/_≡)

• První tabulka obsahuje nedostupné stavy (stav 7).
• Druhá tabulka ukazuje přechodovou funkci po úpravě na totální, přidáním nového stavu N a nasměrováním všech nedefinovaných přechodů do něj.

• Ostatní čtyři tabulky reprezentují postupnou minimalizaci automatu.

Vstup: NFA M = (Q, , , q₀, F).
Výstup: Ekvivalentní DFA M' = (Q', , ', {q₀}, F') bez nedosažitelných stavů a s totální přechodovou funkcí.

Algoritmus

Q' := { {q₀} }; ' := ; F' := ; Done := ;
while (Q' – Done) do
M := libovolný prvek množiny Q' – Done
if M F then F' := F' {M} fi
foreach a do
N :=
Q' := Q' {N}
' := ' {( (M, a),N)} od
Done := Done {M}
od
M' = (Q', , ', {q₀}, F')

Mějme nedeterministický konečný automat :

Převod nedeterministického automatu na deterministický provedeme pomocí algoritmu následovně:

Takto vytvořený automat nemusí být minimální, ale je bez nedosažitelných stavů, s totální přechodovou funkcí.

Konečné automaty se používají např. k lexikální analýze.

Skripta Automaty a formální jazyky I
Slidy k předmětu Automaty a gramatiky

Lukáš Hala, 173454@mail.muni.cz
Pokud si myslíte, že tady něco chybí, přebývá nebo že je něco blbě, tak to prosím upravte

Je potřeba ještě zapracovat poznámky od Jitky Pospíšilové.