autòmat finit indeterminista

m

Matemàtiques

autòmat finit indeterminista

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

Usualment un autòmat finit indeterminista 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 qj ∈ δ(qi, a). S’indiquen els esstats inicials amb fletxes i els finals amb una creu. Els llenguatges acceptats pels autòmats finits indeterministes són els mateixos que els reconeguts pels finits deterministes (regulars) L’avantatge dels indeterministes enfront dels deterministes és la facilitat de maneig i de construcció.