====== 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 =====
<box 90% round blue|Definice 2.1. ((viz skripta Automaty a formální jazyky I, str. 11))>**Konečný automat** //M// je pětice (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//), kde
  * //Q// je neprázdná konečná množina **stavů**,
  * <m>Sigma</m> je konečná množina **vstupních symbolů** (vstupní abeceda),
  * <m>delta</m>: //Q x //<m>Sigma</m> //-> Q// je parciální **přechodová funkce** (v případě nedeterministického konečného automatu je definována jako totální zobrazení <m>delta</m>: //Q x //<m>Sigma</m>// -> 2<sup>Q</sup>//),
  * //q<sub>0</sub>// <m>in</m> //Q// je **počáteční stav**,
  * //F// <m>⊆</m> //Q// je množina **koncových stavů**
</box>
=== 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 

<m>hat{delta}</m>: //Q x //<m>Sigma</m>* //-> Q// definována induktivně vzhledem k délce slova ze <m>Sigma</m>*:
  * <m>hat{delta}</m>(//q//, <m>epsilon</m>) = //q// pro každý stav //q// <m>in</m> //Q//
  * <m>hat{delta}</m>(//q//, //wa//) = 
    *<m>delta</m>(<m>hat{delta}</m>(//q//, //w//), //a//) je-li <m>hat{delta}</m>(//q//, //w//) i <m>delta</m>(<m>hat{delta}</m>(//q//, //w//), //a//) definováno
    *<m>ortho</m> 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// <m>in Sigma</m>* | <m>hat{delta}</m>(//q<sub>0</sub>//,//w//) <m>in</m> //F//}

=== Rozšířená přechodová funkce nedeterministického konečného automatu: ===
<m>hat{delta}</m>: //Q x //<m>Sigma</m>* //-> 2<sup>Q</sup>//, definována induktivně vzhledem k délce slova ze <m>Sigma</m>*:
  * <m>hat{delta}</m>(//q//, <m>epsilon</m>) = {q}
  * <m>hat{delta}</m>(//q//, //wa//) = <m>bigcup{p in hat{delta}(q,w)}{}{delta(p,a)}</m>

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


===== Konstrukce konečného automatu =====
Mějme například jazyk //L// = {//w// <m>in</m> {//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>M = ({lbrace}q_ε, q_a, q_ab, q_aba, q_abaa{rbrace}, {lbrace}a, b{rbrace}, delta, q_ε, {lbrace}q_abaa{rbrace})</m>
kde přechodová funkce <m>delta</m> vypadá následovně:
| <m>delta(q_epsilon, a) = q_a</m>    | <m>delta(q_ab, b) = q_epsilon</m>    |
| <m>delta(q_epsilon, b) = q_epsilon</m>    | <m>delta(q_aba, a) = q_abaa</m>    |
| <m>delta(q_a, a) = q_a</m>    | <m>delta(q_aba, b) = q_ab</m>     | 
| <m>delta(q_a, b) = q_ab</m>    | <m>delta(q_abaa, a) = q_abaa</m>    |
| <m>delta(q_ab, a) = q_aba</m>    | <m>delta(q_abaa, b) = q_abaa</m>    |

==== Tabulkou ====
|  |  ^ a ^ b ^
| -> ^ <m>q_epsilon</m> | <m>q_a</m> | <m>q_epsilon</m> |
|  ^ <m>q_a</m> | <m>q_a</m> | <m>q_ab</m> |
|  ^ <m>q_ab</m> | <m>q_aba</m> | <m>q_epsilon</m> |
|  ^ <m>q_aba</m> | <m>q_abaa</m> | <m>q_ab</m> |
| <- ^ <m>q_abaa</m> | <m>q_abaa</m> | <m>q_abaa</m> |

==== Přechodovým grafem ====
{{home:inf:graf.gif|Přechodový graf}}

==== 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//:
{{:home:inf:vypocetni-strom.gif|Výpočetní strom}}

==== Synchronní paralelní kompozice ====
Pro dané automaty //M<sub>1</sub>// a //M<sub>2</sub>// umožňuje sestrojit automat rozpoznávající **průnik**, **sjednocení** či **rozdíl** jazyků //L//(//M<sub>1</sub>//) a //L//(M<sub>2</sub>).
Nechť //M<sub>1</sub>// = (//Q<sub>1</sub>//, <m>Sigma</m>, <m>delta</m><sub>1</sub>, //q<sub>1</sub>//, //F<sub>1</sub>//), //M<sub>2</sub>// = (//Q<sub>2</sub>//, <m>Sigma</m>, <m>delta</m><sub>2</sub>, //q<sub>2</sub>//, //F<sub>2</sub>//) a přechodové funkce <m>delta</m><sub>1</sub>, <m>delta</m><sub>2</sub> jsou **totální**.
Definujeme konečný automat //M<sub>3</sub>// = (//Q<sub>3</sub>//, <m>Sigma</m>, <m>delta</m><sub>3</sub>, //q<sub>3</sub>//, //F<sub>3</sub>//), kde
  * //Q<sub>3</sub>// = //Q<sub>1</sub>// x //Q<sub>2</sub>// = {(//p//,//q//) | //p// <m>in</m> //Q<sub>1</sub>//, //q// <m>in</m> //Q<sub>2</sub>//}
  * //F<sub>3</sub>// = //F<sub>1</sub>// x //F<sub>2</sub>// = {(//p//,//q//) | //p// <m>in</m> //F<sub>1</sub>//, //q// <m>in</m> //F<sub>2</sub>//}
  * //q<sub>3</sub>// = (//q<sub>1</sub>//, //q<sub>2</sub>//)
  * <m>delta</m><sub>3</sub>( (//p//,//q//),//a//) = (<m>delta</m><sub>1</sub>(//p//,//a//),<m>delta</m><sub>2</sub>(//q//,//a//) )
Potom //L//(//M<sub>3</sub>//) = //L//(//M<sub>1</sub>//) <m>inter</m> //L//(//M<sub>2</sub>//)

Podobně pro sjednocení a rozdíl - zmení sa len množina koncových stavov
  * //F<sub>3</sub>// = (//F<sub>1</sub>// x //Q<sub>2</sub>//) <m>union</m> (//Q<sub>1</sub>// x //F<sub>2</sub>//) = {(//p//,//q//) | //p// <m>in</m> //F<sub>1</sub>// ∨ //q// <m>in</m> //F<sub>2</sub>//} pre zjednotenie
  * //F<sub>3</sub>// = //F<sub>1</sub>// - //F<sub>2</sub>// = {(//p//,//q//) | //p// <m>in</m> //F<sub>1</sub>// ∧ //q// <m>notin</m> //F<sub>2</sub>//} pre rozdiel

== Příklad průniku ==
{{:home:inf:kompozice.gif|Synchronní paralelní kompozice}}

==== Automat pro komplement ====
K automatu //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) s **__totální__ přechodovou funkcí** sestrojíme automat <m>overline{M}</m> rozpoznávající jazyk //co--L//(//M//) jako <m>overline{M}</m> = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //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 [[home:inf:ap8|AP8,IN8 Regulární jazyky]]), kterou můžeme přeformulovat takto:
<box 90% round green|Věta 2.29 Myhill--Nerodova, 2. varianta((viz skripta Automaty a formální jazyky I, str. 26))>Počet stavů libovolného minimálního automatu rozpoznávajícího jazyk //L// je roven indexu prefixové ekvivalence //~<sub>L</sub>//. (Takový konečný automat existuje právě když index //~<sub>L</sub>// je konečný.)
</box>

<box 90% round| //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ů).
</box>

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ů ====
<box 90% round blue| Definice - dosažitelné a nedosažitelné stavy>Nechť //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) je konečný automat. Stav //q// <m>in</m> //Q// nazveme **dosažitelný**, pokud existuje //w// <m>in Sigma</m>* takové, že <m>hat{delta}</m>(//q<sub>0</sub>//, //w//) = //q//. Stav je **nedosažitelný**, pokud není dosažitelný.
</box>

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

**Vstup**: Konečný automat //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//)
**Výstup**: Ekvivalentní automat //M'// bez nedosažitelných stavů.

<box 90% | Algoritmus>//i// := 0
//S<sub>i</sub>// := {//q<sub>0</sub>//}
**repeat** //S//<sub>//i//+1</sub> := //S<sub>i</sub>// <m>union</m> {//q// | <m>exists</m>//p// <m>in</m> //S<sub>i</sub>//, //a// <m>in Sigma</m>: <m>delta</m>(//p//, //a//) = //q//}
//i// := //i// + 1
**until** //S<sub>i</sub>// = //S//<sub>//i//--1</sub>
//Q'// := //S<sub>i</sub>//
//M'// = (//Q'//, <m>Sigma</m>, <m>delta</m>|<sub>//Q'//</sub>, //q<sub>0</sub>//, //F// <m>inter</m> //Q'//)
</box>

//Poznámka//: Zápis <m>delta</m>|<sub>//Q'//</sub> znamená, že funkce <m>delta</m> je omezena na množinu //Q'//.
//Intuitivně//: Množina //S<sub>i</sub>// je množina stavů dosažitelná v automatu v maximálně //i// krocích. 

==== Ztotožnění jazykově ekvivalentních stavů ====
Nechť //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) je konečný automat bez nedosažitelných stavů, jehož přechodová funkce je totální.
<box 90% round blue| Definice - jazykově ekvivalentní stavy>Stavy //p//, //q// nazveme **jazykově ekvivalentní**, psáno //p// ≡ //q//, pokud 
//p// ≡ //q// <m>doubleleftright forall</m>//w// <m>in Sigma</m>* : (<m>hat{delta}</m>(//p//, //w//) <m>in</m> //F// <m>doubleleftright hat{delta}</m>(//q//, //w//) <m>in</m> //F//).
</box>

<box 90% round blue| Definice - Redukt>**Reduktem** automatu //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) nazveme konečný automat //M///<sub>≡</sub> = (//Q///<sub>≡</sub>, <m>Sigma</m>, <m>eta</m>, [//q<sub>0</sub>//], //F///<sub>≡</sub>), kde:
  * Stavy jsou třídy rozkladu //Q///<sub>≡</sub> (třída obsahující stav //q// je [//q//]).
  * Přechodová funkce <m>eta</m> je funkce splňující:
<m>forall</m>//p//,//q// <m>in</m> //Q//, <m>forall</m>a <m>in Sigma</m>: <m>delta</m>(//q//, //a//) = //p// <m>doubleright eta</m>([//q//], //a//) = [//p//].
  * Počáteční stav je třída rozkladu //Q///<sub>≡</sub> obsahující stav //q<sub>0</sub>//.
  * Koncové stavy jsou právě ty třídy rozkladu //Q///<sub>≡</sub>, které obsahují alespoň jeden koncový stav.
</box>

<box 90% round green| Věta> Nechť //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) je konečný automat bez nedosažitelných stavů s totální přechodovou funkcí. Pak //L//(//M//) = //L//(//M///<sub>≡</sub>).
</box>

<box 90% round blue| Definice> Pro každé //i// <m>in bbN</m><sub>0</sub> definujeme binární relaci ≡<sub>//i//</sub> na //Q// předpisem
//p// ≡<sub>//i//</sub> //q// <m>doubleleftright forall</m>//w// <m>in Sigma</m>*.|//w//| <m><=</m> //i// : (<m>hat{delta}</m>(//p//, //w//) <m>in</m> //F// <m>doubleleftright hat{delta}</m>(//q//, //w//) <m>in</m> //F//)
  * //p// ≡<sub>//i//</sub> //q// právě když //p// a //q// nelze "rozlišit" žádným slovem délky <m><=</m> //i//
  * //p// ≡ //q// právě když //p// ≡<sub>//i//</sub> //q// pro každé //i// <m>in bbN</m><sub>0</sub>. (≡ = <m>bigcap{i=0}{infty}{≡}</m><sub>i</sub>)
  - ≡<sub>0</sub> = {(//p//, //q//) | //p// <m>in</m> //F// <m>doubleleftright</m> //q// <m>in</m> //F//}
  - ≡<sub>//i//+1</sub> = {(//p//, //q//) | //p// ≡<sub>//i//</sub> //q// <m>wedge forall</m>//a// <m>in Sigma</m> : <m>delta</m>(//p//, //a//) ≡<sub>//i//</sub> <m>delta</m>(//q//, //a//)}
</box>

=== Algoritmus konstrukce minimálního automatu ===
**Vstup**: Konečný automat //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) bez nedosažitelných stavů s totální přechodovou funkcí
**Výstup**: Redukt //M///<sub>≡</sub>.

<box 90% | Algoritmus>//i// := 0
≡<sub>0</sub> := {(//p//, //q//) | //p// <m>in</m> //F// <m>doubleleftright</m> //q// <m>in</m> //F//}
**repeat**
≡<sub>//i//+1</sub> := {(//p//, //q//) | //p// ≡<sub>//i//</sub> //q// <m>wedge forall</m>//a// <m>in Sigma</m> : <m>delta</m>(//p//, //a//) ≡<sub>//i//</sub> <m>delta</m>(//q//, //a//)}
//i// := //i// + 1
**until** ≡<sub>//i//</sub> = ≡<sub>//i//--1</sub>
≡ = ≡<sub>//i//</sub>
//M///<sub>≡</sub> := (//Q///<sub>≡</sub>, <m>Sigma</m>, <m>eta</m>, [//q<sub>0</sub>//], //F///<sub>≡</sub>)
</box>

== Příklad ==
{{:home:inf:automat_3min.jpg|Konstrukce minimálního automatu}}
  * 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.
<box orange 100% round|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**).
</box>

===== Převod NFA na DFA =====
<box 90% round green| Věta>Pro každý NFA //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) existuje ekvivalentní DFA.
</box>

==== Algoritmus transformace NFA na DFA ====
**Vstup**: NFA //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//).
**Výstup**: Ekvivalentní DFA //M'// = (//Q'//, <m>Sigma</m>, <m>delta</m>', {//q<sub>0</sub>//}, //F//') bez nedosažitelných stavů a s totální přechodovou funkcí.

<box 90% | Algoritmus>//Q'// := { {//q<sub>0</sub>//} }; <m>delta</m>' := <m>varnothing</m>; //F'// := <m>varnothing</m>; //Done// := <m>varnothing</m>;
**while** (//Q'// -- //Done//) <m><>varnothing</m> **do**
//M// := libovolný prvek množiny //Q'// -- //Done//
**if** //M// <m>inter</m> //F// <m><>varnothing</m> **then** //F'// := //F'// <m>union</m> {//M//} **fi**
**foreach** //a// <m>in Sigma</m> **do**
//N// := <m>bigcup{p in M}{}{delta(p,a)}</m>
//Q'// := //Q'// <m>union</m> {//N//}
<m>delta</m>' := <m>delta</m>' <m>union</m> {( (//M//, //a//),//N//)} **od**
//Done// := //Done// <m>union</m> {//M//}
**od**
//M'// = (//Q'//, <m>Sigma</m>, <m>delta</m>', {//q<sub>0</sub>//}, //F'//)
</box>

=== Příklad ===
Mějme nedeterministický konečný automat :

<box 500px left>{{:home:inf:automat_1.jpg|}}</box>

|     ^   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ě:
<box left 100% round orange|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ů.
</box>

Takto vytvořený automat nemusí být minimální, ale je bez nedosažitelných stavů, s totální přechodovou funkcí.
<box 560px left>{{:home:inf:automat_2.jpg|}}</box>

|       ^ a    ^  b   ^
^    -> 1| 12   | 17   | 
^      12| 12   | 137  |
^      17| 126  | 17   |
^     137| 126  | 147  |
^     126| 12   | 1357 |
^     147| 1256 | 17   |
^ <- 1357| 1256 | 1457 |
^ <- 1256| 125  | 1357 |
^ <- 1457| 1256 | 157  |  
^ <-  125| 125  | 1357 | 
^ <-  157| 1256 | 157  |

==== Využití ====
Konečné automaty se používají např. k lexikální analýze.

===== Literatura =====
[[http://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf|Skripta Automaty a formální jazyky I]]
[[http://www.fi.muni.cz/~xstrejc/IB102/slajdy/slajdy_corr.pdf|Slidy k předmětu Automaty a gramatiky]]

===== Vypracoval =====
Lukáš Hala, 173454@mail.muni.cz
Pokud si myslíte, že tady něco chybí, přebývá nebo že je něco blbě, tak to prosím upravte ;-) 

FIXME Je potřeba ještě zapracovat [[http://statnice.dqd.cz/tmp/konecne_automaty.pdf|poznámky od Jitky Pospíšilové]].

~~DISCUSSION~~