Konečný automat

**Konečný automat** je automat (výpočtový model), ktorého množina stavov je konečná. Konečné automaty sú jedným zo základných prostriedkov na popis regulárnych jazykov. Konečné automaty tiež majú aplikácie napríklad pri vyhľadávaní v texte alebo matematickom popise pamäťových obvodov.

Existuje viacero druhov konečných automatov. Základné dva modely sú deterministický konečný automat (DKA) a nedeterministický konečný automat (NKA). Napriek tomu, že NKA dovoľujú podstatne viac, popisná sila oboch modelov je rovnaká. Popísaných tiež bolo množstvo zovšeobecnení týchto základných modelov.

## Deterministický konečný automat

### Definícia DKA

**[[Deterministický konečný automat]]** je pätica (\Sigma, K, q_0, \delta, F), kde:
* \Sigma je vstupná abeceda (neprázdna konečná množina symbolov).
* K je konečná množina stavov.
* q_0 je počiatočný stav, pričom platí q_0 \in K.
* \delta je prechodová funkcia: \delta: K \times \Sigma \rightarrow K, čiže funkcia, ktorá na základe stavu a symbolu zo vstupnej abecedy vráti nový stav
* F je množina akceptačných stavov, je to ľubovoľná (môže byť aj prázdna) podmnožina K. Hovoríme, že DKA akceptuje slovo w, ak výpočet na tomto slove skončí v niektorom z akceptačných stavov.

### Konfigurácia DKA

Konfigurácia deterministického konečného automatu je dvojica (q,w) \in K \times \Sigma^{\ast}, kde *q* je aktuálny stav automatu a *w* je dosiaľ neprečítaná časť vstupného slova.

### Krok výpočtu DKA

Krok výpočtu deterministického konečného automatu je relácia \vdash_A na konfiguráciach DKA definovaná nasledovne: (q,av) \vdash_A (p,v) \iff p = \delta(q,a) .

Pod výpočtom na deterministickom konečnom automate rozumieme ľubovoľnú postupnosť na seba nadväzujúcich výpočtových krokov.

### Jazyk akceptovaný pomocou DKA

Jazyk akceptovaný deterministickým konečným automatom *A* definujeme nasledovne:

:L(A) = \{w\ |\ \exists p \in F: (q_0,w) \vdash_{A}^{\ast} (p,\varepsilon)\}. 

Je to teda množina všetkých slov, na ktorých existuje v automate *A* výpočet končiaci v akceptačnom stave (takému výpočtu sa tiež hovorí akceptačný výpočet).

## Nedeterministický konečný automat

### Definícia NKA

**[[Nedeterministický konečný automat]]** je pätica (\Sigma, K, q_0, \delta, F), kde:
* \Sigma je vstupná abeceda (neprázdna konečná množina symbolov).
* K je konečná množina stavov.
* q_0 je počiatočný stav, pričom platí q_0 \in K.
* \delta je prechodová funkcia: \delta: K \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^K, čiže funkcia, ktorá na základe stavu a symbolu zo vstupnej abecedy vráti množinu nových stavov
* F je množina akceptačných stavov, je to ľubovoľná (môže byť aj prázdna) podmnožina K. Hovoríme, že NKA akceptuje slovo w, ak výpočet na tomto slove skončí v niektorom z akceptačných stavov.

Existujú teda dva podstatné rozdiely medzi NKA a DKA:
* NKA povoľujú prechody na \varepsilon
* Nový stav nie je pre každý prechod určený jednoznačne. Prechodová funkcia vracia celú množinu stavov (pri výpočte sa môže postupovať do ľubovoľného z nich), ktorá môže byť dokonca prázdna.

### Konfigurácia NKA

Konfigurácia nedeterministického konečného automatu sa definuje analogicky, ako pri deterministických konečných automatoch. Je to dvojica (q,w) \in K \times \Sigma^{\ast}, kde *q* je aktuálny stav automatu a *w* je dosiaľ neprečítaná časť vstupného slova.

### Krok výpočtu NKA

Krok výpočtu je relácia  \vdash_A  na konfiguráciach NKA *A* definovaná nasledovne:

: (q,aw) \vdash_A (p,w) \iff p \in \delta(p,a) .

### Jazyk akceptovaný pomocou NKA

Jazyk akceptovaný nedeterministickým konečným automatom *A* je množina

:L(A) = \{w\ |\ \exists p \in F: (q_0,w) \vdash_{A}^{\ast} (p,\varepsilon)\}. 

## Ekvivalencia DKA a NKA

V skutočnosti, napriek rozdielnej definícii oboch výpočtových modelov, je ich výpočtová sila rovnaká. Je dokázané, že ku každému nedeterministickému automatu *A* existuje deterministický konečný automat *B* taký, že *L(B) = L(A)*. Opačná inklúzia je zrejmá z faktu, že deterministický automat je špeciálny prípad nedeterministického.

## Externé odkazy
* 

Kategória:Formálne jazyky
Kategória:Teória automatov