Konečný automat

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

Definícia DKA[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

Definícia NKA[upraviť | upraviť zdroj]

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 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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

  • FILIT – zdroj, z ktorého pôvodne čerpal tento článok.
Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.