Končni avtomat

Iz MaFiRaWiki


(Deterministični) končni avtomat je stroj, ki razpoznava besede nad dano abecedo in ima končno mnogo stanj. Pomika se po vhodni besedi od leve proti desni in skače iz stanja v stanje, v odvisnosti od prebrane vsebine in trenutnega stanja. Beseda je razpoznana, če se na koncu ustavi v enem od izbranih končnih stanj. Na začetku računanja je bralna glava nad prvim simbolom (če je beseda neprazna) in v izbranem, začetnem stanju.

Končni avtomat K opišemo kot peterico K = (Σ,Q,q0,F,d), pri čemer je:

Delovanje

Pravimo, da končni avtomat K prepozna besedo w \in \Sigma^*, če velja:

  • w = ε je prazna beseda in q_0 \in F, ali
  • w = c v, c \in \Sigma, v \in \Sigma^* in avtomat (Σ,Q,d(c,q0),F,d) prepozna besedo v.

Razpoznavanje lahko opišemo tudi kot razširitev prehodne funkcije d : \Sigma \times Q \to Q na D : \Sigma^* \times Q \to Q:

  • D(ε,q) = q
  • D(cv,q) = D(v,d(c,q))

Avtomat sprejme besedo w, če je D(w,q_0) \in F.

To definicijo si lahko predstavljamo takole: avtomat po vrsti (od leve proti desni) pregleduje znake v besedi w. Ko prebere znak c se premakne iz trenutnega stanja q v novo stanje d(c,q). Če je ob koncu besede avtomat v enem od končnih stanj, besedo sprejme, sicer jo zavrne. Množico L(K) = \{w \in \Sigma^* \mid D(w,q_0) \in F\} vseh besed, ki jih avtomat K sprejme, je jezik, ki ga avtomat prepozna.

Jeziki, ki jih razpoznavajo končni avtomati so natanko regularni jeziki.

Prikaz z usmerjenim grafom

Končni avtomat lahko prikažemo z digrafom oziroma usmerjenim omrežjem. Vozlišča so stanja, loki pa prikazujejo prehodno funkcijo. Utež na loku je znak iz abecede. S posebnim dogovorom lahko označimo začetno in končna stanja.

Zgled

Končni avtomat, ki razpoznava jezik:

L = {w ∈ {a,b}*|w = anbm,n > 0, m ≥ 0}

je prikazan z omrežjem. Začetno stanje je pravokotnik, končni stanji pa sta sivi.

Glej tudi

Osebna orodja