1. El Una computadora digital puede considerarse como una máquina .de hecho, muchos tipos de maquinas pueden modelarse utilizando una estructura llamada maquina de estado finito (FSM).
  2. CADENAS DE ENTRADA Y SALIDAS PARA UNA FSM
  3. 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 .si x =x 1,x2,…xn es la cadena de entrada , la cadena de salida correspondiente y = y1,y2, ….y n esta dada por donde.
  4. AUTÓMATA DE ESTADOS FINITOS (FSA)
  5. Un autómata de estados finitos, denotado como M = {S, I, f, s0, A}, es un modelo abstracto de una maquina que consiste en un conjunto finito S de estados, un alfabeto de entrada finito I una función de transición f que asigna un nuevo estado a cada par de estado y entrada, un estado inicial s0 y un subconjunto A de S consiste en los estados de aceptación.
  6. 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.
  7. Lenguaje aceptado por un FSA
  8. FSA DETERMINÍSTICO Y NO DETERMINÍSTICO
  9. 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).
  10. LENGUAJE ACEPTADO POR UN NFA
  11. 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. Ya se ha señalado que si dos FSA aceptan el mismo lenguaje, estos son equivalentes.
  12. CONVERSION DE UN NFA EN UN DFA EQUIVALENTE
  13. Considérese que el NFA dado es M= {S, I, f so, A} y sea M’ el DFA equivalente que se requiere. 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.