- muchos tipos de máquinas, pueden modelarse utilizando una estructura llamada máquina de estado finito (FSM).
- En cada paso en el tiempo una FSM está en cierto estado interno, lee una entada y ve una salida que depende solo de su estado interno y la interna cambia a su estado interno.
Una FSM suele representarse en forma compacta por medio de una tabla llamada tabla de estados o tabla de transición o mediante un diagrama que recibe el nombre de diagrama de estados o diagrama de transición
- CADENAS DE ENTRADA Y SALIDASPARA UNA FSM
- Una FSM genera una cadena de salida correspondiente a una cadena de entrada puesto que cada transición produce una salida, una cadena de entrada también produce una cadena de salida correspondiente.
- AUTOMATA DE ESTADOS FINITOS (FSA)
- Un tipo especial de FSM que se lleva autómata de estados finitos (FSA) es de interés especial ya que puede reconocer cadenas de lenguaje y un autómata de estados finitos también se llama aceptor de estados finitos.
Algunas veces un FSM se denota como M=(S;I,O,f,g,so) donde las letras tienen el mismo significado que en un FSM, pero O consiste en solo dos símbolos de salida 0 y 1 que se toma como un estado de aceptación.
- LENGUAJE ASEPTADO 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.
El conjunto de todas las cadenas que son aceptadas por M se le conoce como lenguajes aceptados y reconocido por M. por ejemplo la cadena abbab es aceptada y la cadena que acaba es rechazada por la FSM cuyo diagrama de estado
- FSA DETERMINADO Y NO DETERMINADO
- Si un autómata de estados finitos, la función de transición asigna un único estado siguiente a cada par de estados y entrada, se llama autómata de estados finitos determinados (DFA).
- LENGUAJE ACEPTADO POR UN NFA EQUIVALENTE
- CONVERSION 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 quiere. cada estado. El conjunto de símbolos de entrada de M' es lo mismo ya que el símbolo de entrada de M' es alimentado a este estado donde f es la función de transición de M.
Un tipo especial de FSM que se lleva automata de estados finitos(FSA) es de interes especial ya que puede reconocer cadenas de lenguaje y un automata de estados finitos tambien se llama aceptor de estados finitos.
- Una cadena no nula a se dice que será aceptada por un NFA si existe almenos una trayectoria que represente a en el diagrama de estados empezando en el estado inicial y terminando en el estado de aceptación.