| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| msz:konecne_automaty [06. 06. 2012, 17.32:19] – [Úplný DKA] pitel | msz:konecne_automaty [16. 08. 2026, 14.02:58] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1 |
|---|
| ====== Konečné automaty ====== | |
| ===== 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 | |
| |
| ==== Minimální/redukovaný DKA (MDKA) ==== | |
| 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) | |
| |
| ===== Odstranění nedosažitelných stavů ===== | |
| 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>) | |
| |
| ===== Minimalizace KA ===== | |
| 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 na DKA ====== | |
| 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 rozšíreného KA na DKA ==== | |
| |
| 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. | |
| |
| ===== Konstrukce NKA k pravé regulární gramatice ===== | |
| 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> | |
| |
| ===== Konstrukce NKA k levé regulární gramatice ===== | |
| 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 | |
