Resultats de la cerca
Es mostren 1 resultats
autòmat finit determinista
autòmat finit determinista
Matemàtiques
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 q i a q j amb etiqueta a si δ q i , a = q j S’indica l’estat inicial amb una fletxa i els finals amb una creu