Obsah

AP9, IN9 Konečné automaty
Diskuze

AP9, IN9 Konečné automaty

Zadání

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

Definice konečného automatu

Definice 2.1. ¹⁾

Konečný automat M je pětice (Q, Sigma

, q₀, F), kde

Q je neprázdná konečná množina stavů,
je konečná množina vstupních symbolů (vstupní abeceda),
: Q x → Q je parciální přechodová funkce (v případě nedeterministického konečného automatu je definována jako totální zobrazení : Q x → 2^Q),
q₀ Q je počáteční stav,
F Q je množina koncových stavů

Rozšířená přechodová funkce deterministického konečného automatu:

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

hat{delta} : Q x Sigma * → Q definována induktivně vzhledem k délce slova ze Sigma *:

(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 in Sigma * | hat{delta} (q₀,w) F}

Rozšířená přechodová funkce nedeterministického konečného automatu:

hat{delta} : Q x Sigma * → 2^Q, definována induktivně vzhledem k délce slova ze Sigma *:

(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 in Sigma * | hat{delta} (q₀,w) inter F != varnothing }

Konstrukce konečného automatu

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:

Uspořádanou pěticí

$M = ({lbrace}q_ε, q_a, q_ab, q_aba, q_abaa{rbrace}, {lbrace}a, b{rbrace}, delta, q_ε, {lbrace}q_abaa{rbrace})$ kde přechodová funkce delta vypadá následovně:

Tabulkou

	a	b
→



←

Přechodovým grafem

Výpočetním stromem

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:

Synchronní paralelní kompozice

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₁, Sigma , delta ₁, q₁, F₁), M₂ = (Q₂, Sigma , delta ₂, q₂, F₂) a přechodové funkce delta ₁, delta ₂ jsou totální.
Definujeme konečný automat M₃ = (Q₃, Sigma , delta ₃, 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₁) inter 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

Příklad průniku

Automat pro komplement

K automatu M = (Q, Sigma , delta , q₀, F) s totální přechodovou funkcí sestrojíme automat overline{M} rozpoznávající jazyk co–L(M) jako = (Q, Sigma , delta , 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“.

Minimalizace konečného automatu

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:

Věta 2.29 Myhill–Nerodova, 2. varianta²⁾

Počet stavů libovolného minimálního automatu rozpoznávajícího jazyk L je roven indexu prefixové ekvivalence ~_L. (Takový konečný automat existuje právě když index ~_L je konečný.)

Důsledek M-N věty

Minimální konečný automat akceptující jazyk L je určen jednoznačně až na isomorfismus (tj. přejmenování stavů).

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.

Odstranění nedosažitelných stavů

Definice - dosažitelné a nedosažitelné stavy

Nechť M = (Q, Sigma

, q₀, F) je konečný automat. Stav q

Q nazveme dosažitelný, pokud existuje w in Sigma

* takové, že hat{delta}

(q₀, w) = q. Stav je nedosažitelný, pokud není dosažitelný.

Algoritmus pro eliminaci nedosažitelných stavů konečného automatu

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

Algoritmus

i := 0
S_i := {q₀}
repeat S_i+1 := S_i union

{q |

S_i, a

(p, a) = q}
i := i + 1
until S_i = S_i–1 Q' := S_i M' = (Q', Sigma

|_Q', q₀, F inter

Q')

Poznámka: Zápis delta |_Q' znamená, že funkce delta 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.

Ztotožnění jazykově ekvivalentních stavů

Nechť M = (Q, Sigma , delta , 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 doubleleftright forall

* : (

(p, w)

(q, w)

F).

Definice - Redukt

Reduktem automatu M = (Q, Sigma

, q₀, F) nazveme konečný automat M/_≡ = (Q/_≡, Sigma

, [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í:

forall p,q Q, forall a in Sigma : delta (q, a) = p doubleright eta ([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, Sigma

, 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 in bbN

₀ definujeme binární relaci ≡_i na Q předpisem
p ≡_i q doubleleftright forall

*.|w|

i : (

(p, w)

(q, w)

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)

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

Algoritmus konstrukce minimálního automatu

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

Algoritmus

i := 0
≡₀ := {(p, q) | p

F}
repeat ≡_i+1 := {(p, q) | p ≡_i q wedge forall

(p, a) ≡_i delta

(q, a)}
i := i + 1
until ≡_i = ≡_i–1 ≡ = ≡_i M/_≡ := (Q/_≡, Sigma

, [q₀], F/_≡)

Příklad

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.

Praktické vysvětlení algoritmu

Na začátku tabulku přechodové funkce rozdělíme do dvou částí(tříd), do druhé části zaznamenáme výstupní stavy, do první části ty ostatní. Obě části označíme římskými číslicemi. Postupně procházíme stavy automatu který chceme minimalizovat, a pro jednotlivé prvky abecedy zjišťujeme, ve které části tabulky se nachází stav do kterého se při přechodu dostaneme. Číslo této části zapíšeme do tabulky k prvku abecedy u zpracovávaného stavu. (tabulka 3)

Tabulku opět rozdělíme, do částí(tříd) které označíme římskými číslicemi, v každé necháme stavy ze kterých se pod všemi prvky abecedy dostaneme do stejných částí tabulky. Aplikujeme předchozí krok.(tabulka 4,5)

Tento postup aplikujeme dokud každá část tabulky neobsahuje jen stavy přecházející do stejných tříd. Ve výsledné tabulce nezapisujeme názvy stavů, ale jen označení tříd s jejich přechody(tabulka 6).

Převod NFA na DFA

Věta

Pro každý NFA M = (Q, Sigma

, q₀, F) existuje ekvivalentní DFA.

Algoritmus transformace NFA na DFA

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

Algoritmus

Q' := { {q₀} }; delta

' :=

; F' :=

; Done := varnothing

;
while (Q' – Done) <>varnothing

do M := libovolný prvek množiny Q' – Done if M inter

then F' := F' union

{M} fi foreach a in Sigma

do N :=

Q' := Q'

{N}

' :=

{( (M, a),N)} od Done := Done union

{M}
od M' = (Q', Sigma

', {q₀}, F')

Příklad

Mějme nedeterministický konečný automat :

	a	b
→ 1	1,2	1,7
2	-	3
3	-	4
4	5	-
← 5	5	5
6	-	5
7	6	-

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

Praktické vysvětlení algoritmu

Začínáme vstupním stavem, který napíšeme do tabulky (1). Zjistíme množinu stavů, do kterých se dostaneme pomocí prvků abecedy. (pro a 1,2, pro b 1,7). Poté vždy vytvoříme (pokud ještě neexistuje) nový stav pojmenovaný jako sjednocení stavů (pro a 12, pro b 17) a zaznamenáme do tabulky. Vezmeme poté následující nezpracovaný stav v nově tvořené tabulce (12) a zjistíme do jaké množiny stavů se lze dostat ze stavů 1 a 2 a provedeme jejich sjednocení (pro a 1,2 , pro b 1,3,7) poté opět zaznamenáme případný nový stav. Od této chvíle pokračujeme obdobně.

Algoritmus končí, ve chvíli kdy není možné nalézt žádný nový stav. Vstupní stavy zůstávají stejné, koncové stavy jsou ty, které obsahují některý z původních koncových stavů.

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