- Una FSM genera una cadena de salida correspondiente a una cadena de entrada.
Cuando se lee la cadena de entrada símbolo por símbolo (de izquierda derecha),
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.
- CADENAS DE ENTRADA Y SALIDAS PARA UNA FSM
- LENGUAJE ACEPTADP POR UN FSA
- AUTOMATA DE ESTADOS FINITOS (FSA)
Un tipo especial de FSM que se llama autómata de estados finitos (FSA)
es de interés especial ya que puede reconocer cadenas de un lenguaje,
que difiere de una FSM en dos aspectos que no produce una salida y tiene pocos
estados de aceptación o estados finales. Un autómata de estados finitos también
se llama aceptor de estados finitos.
Definición:
Denotado como M = {S, I, f, qo, A}, es un modelo abstracto de una maquina
que consiste en un conjunto finito S de estados, un alfabeto de entrada finitos I,
una función de transición f, que asigna un nuevo estado a cada par de estado y entrada,
un estado inicial qo y un subconjunto A de S considere en los estados de aceptación.
- Maquinas de estados finitos.
- Una computadora digital puede considerarse como una máquina.
De hecho, muchos tipos de máquinas, incluso una computadora,
pueden modelarse utilizando una estructura llamada máquina de estados finitos (FSM).
Definición:
Una máquina de estado finitos denotada como M = {S, I, O, f, g, So}
es un modelo abstracto de una máquina, en el cual consiste en un conjunto
finito S de estados, un conjunto finito I de símbolos de entrada, un
conjunto finito O de símbolos de salida un función de transición f que asigna
un nuevo estado a cada par de estados y entrada,
una función de salida g que asigna una salida a cada estado y entrada, y un estado inicial So.
- Cuando un símbolo de una cadena de entrada se alimenta 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 de 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 por lenguaje aceptado o reconocido por M. Dos autómatas de estados finitos
se dice que son equivalentes, si aceptan el mismo lenguaje.
- FSA determinístico y no determinístico
- AUTOMATA DE ESTADOS FINITOS (FSA)
- Si es 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ísticos (DFA).
Un NFA denota como M = {S, I, f, S, A}, consiste en un conjunto S de estados, un alfabeto de entrada I, una función de transición
que asigna un conjunto de estados a cada par de estado y entrada, un estado final y por ello un subconjunto A de S consiste en estados de aceptación.
En la tabla de estados de un NFA, se dará duna lista de posibles de estados siguientes correspondientes a cada par de estados y valores de entrada.
En el diagrama de estado de un NFM, una arista desde cada estado hasta todos los posibles estados siguientes.
- LENGUAJE ACEPTADO POR UN NFA
- Una cadena no nula α se dice que será aceptada por un NFA
si existe al menos una trayectoria que represente 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.
Por ejemplo, las cadenas aab, aaba, aabaa son aceptadas, pero
las cadenas abb, aabb, abab son rechazadas por el NFA indicado.
Ya se ha señalado que si dos FSA aceptan el mismo lenguaje, estos
son equivalentes. Además cualquier NFA puede convertirse en un DFA
equivalente en virtud del siguiente teorema que se muestra a continuación:
TEOREMA: Si un lenguaje L es aceptado por un NFA, existe entonces un DFA que también acepta a L.
- CONVERSION DE UN NFA EN UN DFA EQUIVALENTE
- Considere que el NFA dado es M = {S, I, f, qo, A} y sea M’ el DFA equivalente que se requiere,
cada estado de M’ será un subconjunto de S. de manera correspondiente el estado inicial de M’ es {qo}.
El conjunto de símbolos de entrada de M’ es el mismo que I, si {q1, q2, q3,… qk}, es un estado de M’ y a
es el símbolo de entrada alimentado a este estado, el siguiente estado de M’ es la unión de los conjuntos f(q1), f(q2),… f(qk),
donde f es la función de transición de M. de tal modo, los estados de M’ son algunos de todos los subconjuntos de S
incluyendo el conjunto vacio Ф, los estados finales de M’ son aquellos que contienen a los estados finales de M.