autòmat finit determinista

m

Matemàtiques

autòmat finit determinista

Estructura de la forma M = (Q, ∑, δ, q0, F) on Q és un conjunt finit no buit, els elements del qual s’anomenen estats; ∑ és un alfabet, anomenat d’entrada; δ : Q ⨉ ∑* → Q és la funció de transició que satisfà  ∀q ∈ Q, ∀x,y ∈ ∑*:δ(q, λ) = q, δ(q, xy) = δ(δ(q, x), y) essent xy la concatenació de x i de y, i λ la paraula buida i ∑* el conjunt de paraules; q0 ∈Q s’anomena estat inicial; F ⊂ Q s’anomena conjunt d’estats finals o acceptadors.

Usualment un autòmat finit determinista es descriu mitjançant el seu diagrama de transicions. Es tracta d’un graf dirigit que té els estats per vèrtex si un arc que va de qi a qjamb etiqueta a si δ(qi, a) = qj. S’indica l’estat inicial amb una fletxa i els finals amb una creu.