- Una computadora digital puede considerase como una máquina. De hecho, muchos tipos de máquinas, incluso una computadora, puede modelarse utilizando una estructura llamada máquina de estados finitos (FSM). Varia versiones de FMS que se usan comúnmente como modelos incluyen un conjunto de estados internos con un estado particular especificado como estado inicial, un alfabeto de entrada, de salida y una función de transición que asigna un estado siguiente a cada par de estado interno y entrada.
- CADENAS DE ENTRADA Y SALIDAS PARA UN FSM
- Un FSM genera una cadena de saluda correspondiente a una cadena de entrada, Cuando se lee la cadena de entrada símbolo por símbolo, cada símbolo de entrada lleva a la FSM de un estado a otro. Puesto que cada transición produce una salida, una cadena de entrada también produce una cadena de salida.
- Si x = x1, x2,…xn es la cadena de entrada, la cadena de salida correspondiente y = y1, y2,…yn está dada por:
Yi = g (si-1, xi) para i = 1, 2,…n,
donde Si = f (si-1, xi) para i = 1, 2,…n.
- AUTÓMATA DE ESTADOS FINITOS (FSA)
- Un tipo especial de FSA que se llama autómata de estados finitos (FSA) es de interés especial ya que no puede reconocer cadenas de un lenguaje. Defiere de una FSM en dos aspectos. No produce una salida y tiene pocos estados de aceptación o estados finales, también se le llama aceptor de estados finitos.
- Lenguaje aceptado por un FSA
- Cuando los símbolos de una cadena de entrada se alimentan secuencialmente a una FSM M estos cambian los estados del autómata de manera sucesiva y el autómata termina en cierto estado. Si el último estado es un estado de aceptación del autómata se dice que la cadena será aceptada o reconocida por M. En otro caso, se afirma que será rechazada por M. El conjunto de todas las cadenas que son aceptadas por M se conoce como lenguaje aceptado o reconocido por M.
- FSA DETERMINÍSTICO Y NO DETERMINÍSTICO
- Si en un autómata de estados finitos, la función de transición asigna un único estado siguiente a cada par de estado y entrada, entonces el FSA se llama autómata de estados finitos determinístico (DFA). El FSA dado en los ejemplos anteriores es de este tipo. Si la función de transición asigna varios estados siguientes a cada par de estado y entrada, el FSA se llama autómata de estados finitos no determinístico (NFA).
- LENGUAJE ACEPTADO POR UN NFA
- Una cadena no nula a se dice que será aceptada por un NFA si existe al menos una trayectoria que representa a a en el diagrama de estados empezando en el estado inicial y terminando en el estado de aceptación. El conjunto de todas las cadenas aceptadas por un NFA recibe el nombre de lenguaje aceptado por el NFA.
- TEOREMA
Si un lenguaje L es aceptado por un NFA, existe entonces un DFA que también acepta a L.
- CONVERSIÓN DE UN NFA EN UN DFA EQUIVALENTE
-
Considérese que el NFA dado es M= {S, I, f so, A} y sea M’ el DFA equivalente que se requiere. Cada estado M’ será un subconjunto de S. De manera correspondiente el estado inicial de M’ es {s0}.
El conjunto de símbolos de entrada de M’ es el mismo que I. si {S₁, s₁,…S₁} es un estado de M’ y a es el símbolo de entrada alimentando a este estado, el siguiente estado de M’ es la unión de los conjuntos f (S₁), f (S₂),…, f (S₁), donde f es la función de transición de M. De tal modo, los estados de M’ son alguno de todos los subconjuntos de S incluyendo el conjunto vacío . Los estados finales de M’ son aquellos que contienen a los estados finales de M.