Konečné automaty

Úkol z TINu 2010, Úkol z TINu 2011

Definice (nedeterministického) KA (NKA)

M = (Q, Σ, δ, q₀, F)

Q – konečná množina stavů

Σ – konečná vstupní abeceda

δ – funkce přechodu (zobrazení Q × Σ → 2Q)

q₀ – počáteční stav (q₀ ∈ Q)

F – množina koncových stavů (F ⊆ Q)

Konfigurace

Dvojice (q, w) ∈ Q × Σ* tj. stav a zbývající vstup

Počáteční konfigurace

Dvojice (q₀, w) tj. počáteční stav a celý vstup

Koncová konfigurace

Dvojice (q ∈ F, ε) tj. některý koncový stav a prázdný vstup

Přechod ⊢

Změna jedné konfigurace na jinou jednou aplikací funkce přechodu (přečtení jednoho znaku ze vstupu a změna stavu)

⊢ᵏ – k přechodů po sobě

⊢⁺ – libovolný počet přechodů (> 0) (tranzitivní uzávěr relace přechodu)

⊢* – libovolný počet přechodů (tranzitivní a reflexivní uzávěr relace přechodu)

Jazyk příjmaný KA

L(M) = {w | (q₀, w) ⊢* (q, ε) ∧ q ∈ F}

tj. množina všech řetězců pro které KA přejde z počáteční do koncové konfigurace

Rozlišitelné stavy

Stavy jsou rozlišitelné pokud existuje nějaký vstupní řetězec pro který automat z jednoho stavu skončí v koncovém stavu a z druhého ne.

Formálně: Stavy p, q jsou rozlišitelné pokud ∃ w ∈ Σ*: (p, w) ⊢* (p₁, ε) ∧ (q, w) ⊢* (q₁, ε) a právě jeden z p₁, q₁ je v F

Jazyky přijímané KA jsou jazyky třídy 3 Chomského hierarchie (regulární jazyky).

Varianty konečných automatů

Rozšířený KA

Liší se definice funkce přechodu δ: (Q × (Σ ∪ {ε}) → 2Q, tj. je rozšířený o ε-přechody.

Deterministický konečný automat (DKA)

Liší se definice funkce přechodu δ: Q × Σ → Q ∪ {nedef}, nedef ∉ Q, tj. pro každou konfiguraci existuje jen jeden možný přechod.

Jsou ekvivalentní NKA

Každý NKA lze převést na DKA

Úplný DKA

Funkce přechodu je definována pro všechny kombinace vstupního znaku a stavu. tj. δ je totální funkcí na Q × Σ.

Pro případy, kdy neúplná KA nemohl pokračovat (a tím odmítl vstup) zavádíme speciální nekoncový stav ERROR (SINK, T, …) do kterého, když se automat dostane tak jej nemůže opustit (tj. po přečtení celého vstupu je stále v nekoncovém stavu a tak vstup odmítne).

DKA bez nedosažitelných stavů

Je DKA ve kterém eliminujeme nedosažitelné stavy. To jsou ty stavy, do kterých se nedá z počátečního stavu dostat.

Minimální/redukovaný DKA (MDKA)

Je DKA bez nedosažitelných stavů ve kterém nejsou žádné 2 stavy nerozlišitelné:

Redukujeme nerozlišitelné stavy

Odstraníme přebytečné stavy (stavy nemající vliv na přijímání vstupního řetězce)

V minimálním DKA jsou stavy množiny stavů z původního automatu, pričemž v každé množině jsou stavy navzájem nerozlišitelné (jde v podstatě o třídy ekvivalence vzhledem k relaci nerozlíšitelnosti).

Odstranění nedosažitelných stavů

Převod DKA (Q, Σ, δ, q₀, F) na DKA bez nedosažitelných stavů (Q′, Σ, δ′, q₀, F′)

Najdeme všechny dostupné stavy Qᵢ

i = 0

Q₀ = {q₀} (tj. v nultém kroku je dostupný pouze počáteční stav)

repeat

Qᵢ₊₁ = Qᵢ ∪ {q | ∃ p ∈ Qᵢ ∃ a ∈ Σ: δ(p, a) = q} (tj. do množiny dostupných stavů přidáme všechny stavy do kterých se dá libovolným symbolem přejít z některého dostupného stavu z minulého kroku)

i++ (tj. přejdeme k dalšímu kroku)

until Qᵢ = Qᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina dostupných stavů nezměnila)

Nový automat sestavíme jako:

Q′ = Qᵢ tj. použijeme pouze dosažitelné stavy

Použijeme pouze přechody obsahující dosažitelné stavy

Použijeme pouze koncové stavy z množiny dosažitelných stavů (F′ = F ∩ Qᵢ)

Minimalizace KA

Převod DKA (Q, Σ, δ, q₀, F) na MDKA (Q′, Σ, δ′, q₀′, F′):

Převedeme na DKA bez nedostupných stavů

Určíme relaci nerozlišitelnosti stavů (≡ⁱ)

i = 0

≡⁰ = {(p, q) | p ∈ F ⇔ q ∈ F} (tj. na začátku rozlišujeme pouze dvě třídy – koncové a nekoncová stavy)

repeat

≡ⁱ⁺¹ = {(p, q) | p ≡ⁱ q ∀ a ∈ Σ: δ(p, a) ≡ⁱ δ(q, a)} (tj. prvky zůstanou ekvivalentní pouze pokud v minulém kroku vyšly ekvivalentní a všechny možné výsledky odpovídajících přechodů z nich jsou také ekvivalentní)

i++

until ≡ⁱ = ≡ⁱ⁻¹ (tj. končíme pokud v posledník kroku nedošlo k žádným změnám tříd ekvivalence)

Sestavíme nový automat jako:

Q′ = Q \ ≡ⁱ (tj. nové stavy odpovídají třídám ekvivalence původních stavů podle relace nerozlišitelnosti)

∀ p, q ∈ Q ∀ a ∈ Σ: δ′([p], a) = [q] ⇔ δ(p, a) = q (tj. nové přechody jsou mezi těmi třídami ekvivalence u ktrých existuje alespoň jeden odpovídající přechod mezi některými jejich prvky)

q₀′ = [q₀] (tj. počáteční stav je ta třída ekvivalence, která obsahuje původní počáteční stav)

F′ = {[q] | q ∈ F} (tj. koncové stavy jsou ty třídy ekvivalence, která obsahují některý z původních koncových stavů)

Převod NKA na DKA

Převod NKA (Q, Σ, δ, q₀, F) na DKA (Q′, Σ, δ′, q₀′, F′):

Q′ = (2Q \ {∅}) ∪ {nedef} (tj. nové stavy označujeme jako množiny původních stavů, místo prázdné množiny máme spec. stav {nedef})

Pro všechna S ∈ 2Q \ {∅} a pro všechna a ∈ Σpolož:

δ′(S, a) = ∪ δ(q, a) pro q ∈ S

Je-li δ′(S, a) = {∅} polož δ′(S, a) = nedef

Tj. pro všechny možné stavy S DKA a všechny možné znaky a na vstupu určíme následující stav jako sjednocení všech stavů do kterých vedou přechody se znakem a ze stavů v množině S. Pokud žádné takové přechody neexistují je přechod nedefinovaný.

F′ = {S, S ∈ 2Q ∧ S ∩ F ≠ ∅} (tj. za koncové stavy DKA považujeme všechny stavy jejichž množina obsahuje alespoň jeden koncový stav z NKA)

Alternativní přístup

Využíváme skutečnost, že většina stavů z 2Q je nedostupná

Stavy DKA vznikají jako množiny stavů NKA

Určíme počáteční stav DKA jako q₀ a přidáme si ho na seznam nezpracovaných stavů

Pro každý nezpracovaný stav X:

Vezmeme všechny stavy NKA, které jsou součástí množiny X – označíme {X}

Podíváme se jaké všechny symboly se vyskytují u přechodů vedoucích z {X}

Pro každý z těchto symbolů pak:

Určíme množinu stavů NKA (označíme Y) do kterých se lze dostat nějakým přechodem s tímto symbolem z některého z některého stavu v {X}

Do DKA přidáme přechod s tímto symbolem vedoucí z X do Y

Pokud Y dosud není součástí DKA přidáme ho na seznam nezpracovaných stavů

Stav X označíme za zpracovaný a přidáme ho do množiny stavů DKA

Pokud jsou nějaké nezpracovaná stavy jdeme zpět ke 3

Za koncové stavy DKA považujeme všechny stavy jejichž množina obsahuje alespoň jeden koncový stav z NKA

Převod rozšířeného KA na DKA

Převod RKA na DKA je stejný jako převod NKA na DKA, akorát ve 2. kroku sa jako δ′(S, a) nebere sjednocení, ale ε-uzávěr množiny, která vznikne tímto sjednocením.

Konstrukce NKA k pravé regulární gramatice

Gramatika G = (N, Σ, P, S) na NKA (Q, Σ, δ, q₀, F)

Q = N ∪ {qF} (stavy NKA odpovídají nonterminálům gramatiky s přidaným qF)

Σ = Σ (tj. vstupní abeceda a množina terminálů jsou stejné)

q₀ = S (tj. počátační stav odpovídá počátečnímu nonterminálu gramatiky)

Je-li S → ε pravodlo z P pak F = {S, qF} jinak F = {qF} (tj. koncové stavy jsou qF a v případě, že v gramtice je i prázdný řetezec tak i S)

Funkci přechodů definujeme:

Je-li A → aB pravidlo z P, pak δ(A, a) obsahuje B

Je-li A → a pravidlo z P, pak δ(A, a) obsahuje qF

Konstrukce NKA k levé regulární gramatice

Gramatika G = (N, Σ, P, S) na NKA (Q, Σ, δ, q₀, F)

Q = N ∪ {q₀} (stavy NKA odpovídají nonterminálům gramatiky s přidaným q₀)

Σ = Σ (tj. vstupní abeceda a množina terminálů jsou stejné)

q₀ = S (tj. počátační stav odpovídá počátečnímu nonterminálu gramatiky)

Je-li S → ε pravodlo z P pak F = {S, q₀} jinak F = {S} (tj. koncové stavy jsou S a v případě, že v gramtice je i prázdný řetezec tak i q₀)

Funkci přechodů definujeme:

Je-li A → Ba pravidlo z P, pak δ(B, a) obsahuje A

Je-li A → a pravidlo z P, pak δ(q₀, a) obsahuje A