1.4. AUTÓMATAS FINITOS NO DETERMINISTAS. MAQUINA CONCEPTUAL.

     La única diferencia con los anteriores está en que en la transición en un estado determinado puede haber, para un mismo símbolo, más de un arco o no haber ninguno.

     Decimos que un autómata finito no determinista acepta una cadena si es posible que su análisis deje a la máquina en un estado de aceptación. Decimos si es posible, pues si se toma el camino equivocado no se aceptaría una cadena que podría ser válida (una cadena del lenguaje aceptado por este autómata, designado por L(M).

     Formalmente el autómata finito no determinista consiste en una quíntupla (S, S , r, i , F), donde

  • S es un conjunto finito de estados
  • S es el alfabeto de la máquina
  • r es un subconjunto de S x S x S (posibles transiciones de la máquina)
  • i (un elemento de S) es el estado inicial
  • F (un subconjunto de S) es la colección de estados de aceptación

     Un autómata de la forma (S, S, r , i, F) acepta la cadena no vacía x1x2...xn si y solo si existe una serie de estados s0,s1,...sn tal que s0= i y sn Î F y para cada entero j de 1 a n (sj-1,xj,sj) está en r . Además, las tripletas (p,x,q) y (p,x,r), donde q y r son estados que pueden ser distintos, pueden estar en r, diciéndose que al leer el símbolo x en el estado p se puede pasar al estado q o al r.

     Para hacer un programa de un autómata no determinista se podría hacer probando todas las rutas una a una hasta que se terminasen o se aceptase la cadena, lo cual no es eficiente por la cantidad de memoria necesaria (crece exponencialmente con el número de estados).

     Para analizar una cadena en un autómata finito no determinista vamos a seguir todas las transiciones posibles en paralelo (atravesamos todas las rutas a la vez); la cadena se aceptará si alguna de las rutas acaba en un estado de aceptación. Nuestro estado en un momento dado ya no se hallará determinado por un estado del diagrama de transiciones, sino por la colección de los estados actuales de todas las rutas posibles; si K es la colección de estados actuales, al leer x del flujo de entrada obtendríamos un nuevo estado actual, representada por la colección de los estados a los que es posible llegar desde un estado K. Al pasar de conjuntos de estados a conjuntos de estados, se evitan los retrocesos (las rutas sucesivas distintas) además de superar el no determinismo del autómata.

TEOREMA.- Para cada autómata finito no determinista, existe un autómata finito determinista que acepta exactamente el mismo lenguaje.

DEMOSTRACIÓN

     Sea M = (S, S, r , i, F), definimos entonces otro autómata M' determinista representado por el quíntuplo (S', S, d , i',F') donde:

  • S'=P(S) Conjunto de todos los subconjuntos de S (recordar que el conjunto potencia se encuentra incluido el conjunto vacío, que será el estado de captación global)
  • i'={ i} (mismo estado inicial)
  • F' es la colección de subconjuntos de S (estados de S') que contienen, por lo menos, un estado de F (cada uno de los estados de S' dentro de los cuales hay al menos un estado de aceptación de M)
  • d es la función de S' x S a S'; para cada símbolo del alfabeto y estado s' de S', d (s',x) es el estado de S' compuesto por los estados de S a los que es posible llegar desde todos los estados s de s' siguiendo un arco con etiqueta x; al ser d una función, M' es finito determinista.

M y M' aceptan exactamente las mismas cadenas, es decir, el mismo lenguaje; para demostrarlo hay que hacerlo sobre el enunciado: Para cada ruta en M del estado i al estado sn , que recorre arcos w1, w2,..., wn existe una ruta en M' del estado i' al estado sn ' que recorre los arcos w1, w2,..., wn de modo que sn Î s'n y viceversa (para cada ruta en M' de i ' recorriendo arcos w1, w2,..., wn y cada sn Î s'n, existe una ruta en M de i a sn que recorre arcos w1, w2,..., wn ). (Se demuestra por inducción).

     Del anterior teorema se deduce que el no determinismo no permite que se acepte un conjunto mayor de cadenas.

TEOREMA.- Para cualquier alfabeto S, {L(M) es un autómata finito determinista con alfabeto S} = { L(M) es un autómata finito no determinista con alfabeto S}.

DEMOSTRACIÓN             Se trata de una repetición del teorema anterior

     A partir de este momento sólo se va a hacer referencia a autómatas finitos sin distinguir entre deterministas y no deterministas (a los autómatas finitos también se les llama autómatas regulares)

 

principal  anterior  siguiente

 

© 1999 Roberto de la Fuente López. Todos los derechos reservados

Fecha de actualización: 15 de abril de 1999