====== Konečné automaty ======
[[pitel:tin:ukoly:2010:1#priklad 2|Úkol z TINu 2010]], [[pitel:tin:ukoly:2011:1#priklad_2|Ú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// × //Σ// -> 2<sup>//Q//</sup>)
  * //q//₀ -- **počáteční stav** (//q//₀ ∈ //Q//)
  * //F// -- **množina koncových stavů** (//F// ⊆ //Q//)

  * **Konfigurace**
    * Dvojice (//q//, //w//) ∈ //Q// × //Σ//<sup>*</sup> 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)
    * ⊢<sup>*</sup> -- libovolný počet přechodů (tranzitivní a reflexivní uzávěr relace přechodu)
  * Jazyk příjmaný KA
    * //L//(//M//) = {//w// | (//q//₀, //w//) ⊢<sup>*</sup> (//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// ∈ //Σ//<sup>*</sup>: (//p//, //w//) ⊢<sup>*</sup> (//p//₁, //ε//) ∧ (//q//, //w//) ⊢<sup>*</sup> (//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// × (//Σ// ∪ {//ε//}) -> 2<sup>//Q//</sup>, 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//′ = (2<sup>//Q//</sup> \ {∅}) ∪ {''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// ∈ 2<sup>//Q//</sup> \ {∅} 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// ∈ 2<sup>//Q//</sup> ∧ //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 2<sup>//Q//</sup> 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// ∪ {//q<sub>F</sub>//} (stavy NKA odpovídají nonterminálům gramatiky s přidaným //q<sub>F</sub>//)
  - //Σ// = //Σ// (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<sub>F</sub>//} jinak //F// = {//q<sub>F</sub>//} (tj. koncové stavy jsou //q<sub>F</sub>// 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 //q<sub>F</sub>//
===== 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//