Konečné automaty

Úkol z TINu 2010, Úkol z TINu 2011

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

• Q – konečná množina stavů
• Σ – konečná vstupní abeceda
• δ – funkce přechodu (zobrazení Q × Σ → 2^Q)
• 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).

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

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

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).

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.

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

1. Redukujeme nerozlišitelné stavy
2. Odstraníme přebytečné stavy (stavy nemající vliv na přijímání vstupního řetězce)
3. 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).

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

1. Najdeme všechny dostupné stavy Qᵢ
   1. i = 0
   2. Q₀ = {q₀} (tj. v nultém kroku je dostupný pouze počáteční stav)
   3. repeat
      1. 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)
      2. i++ (tj. přejdeme k dalšímu kroku)
   4. until Qᵢ = Qᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina dostupných stavů nezměnila)
2. 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ᵢ)

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

1. Převedeme na DKA bez nedostupných stavů
2. Určíme relaci nerozlišitelnosti stavů (≡ⁱ)
   1. i = 0
   2. ≡⁰ = {(p, q) | p ∈ F ⇔ q ∈ F} (tj. na začátku rozlišujeme pouze dvě třídy – koncové a nekoncová stavy)
   3. repeat
      1. ≡ⁱ⁺¹ = {(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í)
      2. i++
   4. until ≡ⁱ = ≡ⁱ⁻¹ (tj. končíme pokud v posledník kroku nedošlo k žádným změnám tříd ekvivalence)
3. 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 (Q, Σ, δ, q₀, F) na DKA (Q′, Σ, δ′, q₀′, F′):

1. Q′ = (2^Q \ {∅}) ∪ {nedef} (tj. nové stavy označujeme jako množiny původních stavů, místo prázdné množiny máme spec. stav {nedef})
2. Pro všechna S ∈ 2^Q \ {∅} 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ý.
3. F′ = {S, S ∈ 2^Q ∧ S ∩ F ≠ ∅} (tj. za koncové stavy DKA považujeme všechny stavy jejichž množina obsahuje alespoň jeden koncový stav z NKA)

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

1. Stavy DKA vznikají jako množiny stavů NKA
2. Určíme počáteční stav DKA jako q₀ a přidáme si ho na seznam nezpracovaných stavů
3. Pro každý nezpracovaný stav X:
   1. Vezmeme všechny stavy NKA, které jsou součástí množiny X – označíme {X}
   2. Podíváme se jaké všechny symboly se vyskytují u přechodů vedoucích z {X}
   3. Pro každý z těchto symbolů pak:
      1. 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}
      2. Do DKA přidáme přechod s tímto symbolem vedoucí z X do Y
      3. Pokud Y dosud není součástí DKA přidáme ho na seznam nezpracovaných stavů
   4. Stav X označíme za zpracovaný a přidáme ho do množiny stavů DKA
4. Pokud jsou nějaké nezpracovaná stavy jdeme zpět ke 3
5. Za koncové stavy DKA považujeme všechny stavy jejichž množina obsahuje alespoň jeden koncový stav z NKA

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.

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

1. Q = N ∪ {q_F} (stavy NKA odpovídají nonterminálům gramatiky s přidaným q_F)
2. Σ = Σ (tj. vstupní abeceda a množina terminálů jsou stejné)
3. q₀ = S (tj. počátační stav odpovídá počátečnímu nonterminálu gramatiky)
4. Je-li S → ε pravodlo z P pak F = {S, q_F} jinak F = {q_F} (tj. koncové stavy jsou q_F a v případě, že v gramtice je i prázdný řetezec tak i S)
5. 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 q_F

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

1. Q = N ∪ {q₀} (stavy NKA odpovídají nonterminálům gramatiky s přidaným q₀)
2. Σ = Σ (tj. vstupní abeceda a množina terminálů jsou stejné)
3. q₀ = S (tj. počátační stav odpovídá počátečnímu nonterminálu gramatiky)
4. 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₀)
5. 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