Caracteristicas de Automatas Finitos



Características de maquinas de Estado Finito (DFA y NFA)

Maquinas de estado finito
Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en formaautomática sobre una entrada para producir una salida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento sebasa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata sedesplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

Representación grafica de autómatas finitos
1) Los estados se representan connúmeros, que, si es preciso, llevan en su interior el nombre que se quiere dar al estado para identificarlo
2) El estado inicial se indicara con una pequeña flecha que incida sobre éste.
3) Losestados aceptadores se indicaran con una pequeña cruz que salga de los mismos
4) Las posibles transiciones, en función de los símbolos leídos, se indicaran con flechas que van de un estado a otro (o a simismo). Estas flechas se etiquetaran con el símbolo que provoca el cambio.



Autómatas finitos deterministas (DFA)

-Numero finito de estados
-Un único estado inicial
-Para cada estado una, ysolo una, transición para cada símbolo

Se define como un quíntuplo de la forma (Q, Σ, q0, F, δ),
Donde:
---Q: es un conjunto finito de estados
---Σ: es el alfabeto de entrada
---q0: es elestado inicial (q0 ∈ Q)
---F: es un conjunto de estados aceptadores (F ⊂ Q)
--- δ: llamada función transición, es una aplicación de la forma:
δ: Q×Σ→ Q


Autómatas finitos indeterminista (NFA)-Tiene más de un estado inicial, o
-tiene transiciones definidas de forma múltiple, o
-tiene transiciones no definidas

Se define como un quíntuplo de la forma (Q, Σ.I, F, δ)
Donde:
---Q: es un...