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 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 DKA 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

• FILIT – zdroj, z ktorého pôvodne čerpal tento článok.