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

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 DKA 

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 DKA 

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ý automat 

 Definícia NKA 

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 NKA 

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 NKA 

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

.

 Jazyk akceptovaný pomocou NKA 

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

 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