Resultats de la cerca
Es mostren 2 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
autòmat finit indeterminista
autòmat finit indeterminista
Matemàtiques
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 q i a q j amb etiqueta a si q j ∈ δ q i , 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ó