1. Una computadora digital puede considerarse como una maquina de echo muchos tipos de maquina ,incluso una computadora puede modelarse y llamarse estados finitos (FSM)
2. En cada paso en el tiempo una FSM esta 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.
3. Una FSM suele representarse en forma compacta por medio de una tabla llamada tabla de estados o tabla de transcision o mediante un diagrama que recibe el nombre de diagrama de estados o diagrama de transcision
4. CADENAS DE ENTRADA Y SALIDASPARA UNA FSM
5. Una FSM genera una cadena de salida correspondiente a una cadena de entrada puesto que cadatranscision produce una salida, una cadena de entrada tambien produce una cadena de salida correspondiente.
6. AUTOMATA DE ESTADOS FINITOS
7. 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.
8. 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 simbolos de salida 0 y 1 que se toma como un estado de aceptacion.
9. En otras palabra, un NFA denotado como M= (S,I,f,so,A) consiste en un conjunto S de estados, un alfabeto de entrada I, una funcion de transcision que asigna un conjunto de estados a cada par de estado y entrada, un estado final y por ello un subconjuntoA de S consistente en estados de aceptacion.
10. LENGUAJE ACEPTADO POR UN NFA EQUIVALENTE
11. Una cadena no nula a se dice que sera aceptada `por un NFA si existe almenos una trayectoria que represente a a en el diagrama de estados empezando en el estado inicial y terminando en el estado de aceptacion.
12. FSA DETERMINADO Y NO DETERMINADO
13. si un automata de estados finitos, la funcion de transcison asigna un unico estado siguiente a cada par de estados y entrada, se llama automata de estados finitos determinados (DFA).
14. CONVERSION DE UN NFA EN UN DFA EQUIVALENTE
15. Considerese 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 simbolos de entradade M' es lo mismo ya que el simbolo de entradade M' es alimentado a este estado dode f es la funcion de transcision de M.