Otvoriť hlavné menu

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ý automatUpraviť

Definícia DKAUpraviť

Deterministický konečný automat je pätica  , kde:

  •   je vstupná abeceda (neprázdna konečná množina symbolov).
  •   je konečná množina stavov.
  •   je počiatočný stav, pričom platí  .
  •   je prechodová funkcia:  , čiže funkcia, ktorá na základe stavu a symbolu zo vstupnej abecedy vráti nový stav
  •   je množina akceptačných stavov, je to ľubovoľná (môže byť aj prázdna) podmnožina  . Hovoríme, že DKA akceptuje slovo  , ak výpočet na tomto slove skončí v niektorom z akceptačných stavov.

Konfigurácia DKAUpraviť

Konfigurácia deterministického konečného automatu je dvojica  , kde q je aktuálny stav automatu a w je dosiaľ neprečítaná časť vstupného slova.

Krok výpočtu DKAUpraviť

Krok výpočtu deterministického konečného automatu je relácia   na konfiguráciach DKA definovaná nasledovne:  .

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 DKAUpraviť

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

 

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ý automatUpraviť

Definícia NKAUpraviť

Nedeterministický konečný automat je pätica  , kde:

  •   je vstupná abeceda (neprázdna konečná množina symbolov).
  •   je konečná množina stavov.
  •   je počiatočný stav, pričom platí  .
  •   je prechodová funkcia:  , čiže funkcia, ktorá na základe stavu a symbolu zo vstupnej abecedy vráti množinu nových stavov
  •   je množina akceptačných stavov, je to ľubovoľná (môže byť aj prázdna) podmnožina  . Hovoríme, že NKA akceptuje slovo  , 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  
  • 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 NKAUpraviť

Konfigurácia nedeterministického konečného automatu sa definuje analogicky, ako pri deterministických konečných automatoch. Je to dvojica  , kde q je aktuálny stav automatu a w je dosiaľ neprečítaná časť vstupného slova.

Krok výpočtu NKAUpraviť

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

 .

Jazyk akceptovaný pomocou NKAUpraviť

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

 

Ekvivalencia DKA a NKAUpraviť

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é odkazyUpraviť