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

Je DKA bez nedosažitelných stavů ve kterém nie sú žiadne 2 stavy nerozlíšiteľné: * 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álnom DKA sú stavy množiny stavov z pôvodného automatu, pričom v každej množine sú stavy navzájom nerozlíšiteľné (ide v podstate o triedy ekvivalencie vzhladom k relácii nerozlíšiteľnosti)

Převod DKA <math>(Q, \Sigma, \delta, q_0, F)</math> na DKA bez nedosažitelných stavů<math>(S', \Sigma, \delta', q_0, F')</math>

'1)' Najdeme všechny dostupné stavy (<math>S_i</math>) :: <math>i := 0</math> :: <math>S_0 := \{q_0\}</math> (tj. v nultém kroku je dostupný pouze počáteční stav) :: repeat ::: <math>S_{i+1} := S_i \cup \{q | \exists p \in S_i \exists a \in \Sigma : \delta(p, a) = q\}</math> (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) ::: <math>i := i + 1</math> (tj. přejdeme k dalšímu kroku) :: unitil <math>S_i =S_{i-1}</math> (tj. končíme pokud se nám v posledním kroku množina dostupných stavů nezměnila)

'2)' Nový automat sestavíme jako: :: <math>S' = S_i</math> (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ů (<math>F' = F \cap S_i</math>)

Převod DKA <math>(Q, \Sigma, \delta, q_0, F)</math> na MDKA <math>(Q', \Sigma, \delta', q_0', F')</math>

'1)' Převedeme na DKA bez nedostupných stavů

'2)' Určíme relaci nerozlišitelnosti stavů (<math>\equiv^i</math>)

::<math>i := 0</math> ::<math>\equiv^0 := \{(p,q) | p \in F \Leftrightarrow q \in F\}</math> (tj. na začátku rozlišujeme pouze dvě třídy - koncové a nekoncová stavy) :: repeat ::: <math>\equiv^{i+1} := \{(p,q) | p \equiv^i q \forall a \in \Sigma : \delta(p,a) \equiv^i \delta(q,a) \}</math> (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í) ::: <math> i := i + 1</math> :: unitil <math>\equiv^i = \equiv^{i-1}</math> (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: :: <math>Q' = Q / \equiv^i</math> (tj. nové stavy odpovídají třídám ekvivalence původních stavů podle relace nerozlišitelnosti) :: <math>\forall p,q \in Q \forall a \in \Sigma : \delta'([p], a) = [q] \Leftrightarrow \delta(p, a) = q</math> (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) :: <math>q_0' = [q_0]</math> (tj. počáteční stav je ta třída ekvivalence, která obsahuje původní počáteční stav) :: <math>F' = \{[q] | q \in F\}</math> (tj. koncové stavy jsou ty třídy ekvivalence, která obsahují některý z původních koncových stavů)

Převod NKA <math>(Q, \Sigma, \delta, q_0, F)</math> na DKA <math>(Q', \Sigma, \delta', q_0', F')</math>

'1)' <math>Q' = (2^Q \setminus \{\emptyset\}) \cup \{nedef.\}</math>

(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 <math>S \in 2^Q \setminus \{\emptyset\}</math> a pro všechna <math>a \in \Sigma</math> polož: :: <math>\delta'(S, a) = \bigcup_{q \in S} \delta (q, a)</math> :Je-li <math>\delta'(S, a) = \{\emptyset\}</math> polož <math>\delta'(S, a) = nedef.</math>

(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)' <math>F' = \{S, S \in 2^Q \wedge S \cap F \neq \emptyset\}</math>

(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 <math>2^Q</math> je nedostupná)

'1)' Stavy DKA vznikají jako množiny stavů NKA

'2)' Určíme počáteční stav DKA jako <math>\{q_0\}</math> a přidáme si ho na seznam nezpracovaných stavů

'3)' 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

'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

Prevod RKA na DKA je rovnaký ako prevod NKA na DKA, akurát v 2. kroku sa ako <math>\delta'(S,a)</math> neberie zjednotenie, ale <math>\epsilon-uzaver</math> množiny, kotrá vznikne týmto zjednotením.

Gramatika <math>g = (N, \Sigma, P, S)</math> na NKA <math>(Q, \Sigma, \delta, q_0, F)</math>

'1)' <math>Q = N \cup \{q_F\}</math> (stavy NKA odpovídají nonterminálům gramatiky s přidaným <math>q_F</math>)

'2)' <math>\Sigma = \Sigma</math> (tj. vstupní abeceda a množina terminálů jsou stejné)

'3)' <math>q_0 = S</math> (tj. počátační stav odpovídá počátečnímu nonterminálu gramatiky)

'4)' Je-li <math>S \rightarrow \epsilon</math> pravodlo z P pak <math>F = \{S, q_F\}</math> jinak <math>F = \{q_F\}</math> (tj. koncové stavy jsou <math>q_F</math>) a v případě, že v gramtice je i prázdný řetezec tak i S

'5)' funkci přechodů definujeme: :: Je-li <math>A \rightarrow aB</math> pravidlo z P, pak <math>\delta (A, a) obsahuje B</math> :: Je-li <math>A \rightarrow a</math> pravidlo z P, pak <math>\delta (A, a)</math> obsahuje <math>q_F</math>

Gramatika <math>g = (N, \Sigma, P, S)</math> na NKA <math>(Q, \Sigma, \delta, q_0, F)</math>

'1)' <math>Q = N \cup \{q_0\}</math> (stavy NKA odpovídají nonterminálům abecedy s přidaným <math>q_0</math>)

'2)' <math>\Sigma = \Sigma</math> (tj. vstupní abeceda a množina terminálů jsou stejné)

'3)' <math>q_0</math> je počáteční stav

'4)' Je-li <math>S \rightarrow \epsilon</math> pravodlo z P pak <math>F = \{S, q_0\}</math> jinak <math>F = \{S\}</math> (tj. koncové stavy jsou <math>S</math>) a v případě, že v gramtice je i prázdný řetezec tak i <math>q_0</math>

'5)' funkci přechodů definujeme: :: Je-li <math>A \rightarrow Ba</math> pravidlo z P, pak <math>\delta (B, a) obsahuje A</math> :: Je-li <math>A \rightarrow a</math> pravidlo z P, pak <math>\delta (q_0, a)</math> obsahuje A