Automatas Finitos No Deterministicos

Automatas Finitos No Deterministicos

AUTÓMATAS FINITOS NO DETERMINÍSTICOS (NFA’S).

Un autómata finito no determinístico es una quinta tupla ( Q, S , q0, d , F) en donde Q, S , q0 y F (estados, entradas, estado inicial y estados finales) poseen el mismo significado que para un DFA, pero en este caso d es una transformación de Q x S a 2Q. (Recuérdese que 2Q es el conjunto de potencias de Q, el conjunto de todos los subconjuntos de Q). Obsérvese que puesto que d es una relación para todo par (q, s ) compuesto por el estado actual y el símbolo de la entrada, d (q, s ), es una colección de cero o más estados [es decir, d (q, s )Í Q]. Esto indica que, para todo estado q1 se pueden tener cero o más alternativas a elegir como estado siguiente, todas para el mismo símbolo de entrada.

Generalmente el término autómata finito no determinístico se abrevia como NFA de sus siglas en inglés Nondeterministic Finite Automaton. Si M es un NFA, definiremos el lenguaje acepatdo por M por medio de L(M)={w ½ w es una cadena aceptada por M} donde una cadena w es aceptada por M, si M pasa de su estado inicial a su estado de aceptación o final al recorrer w (w es consumida en su totalidad).

Observe ahora el diagrama de transición de la figura 2.5

 Para ver el gráfico seleccione la opción “Descargar” del menú superior

El NFA descrito anteriormente acepta el lenguaje formado por cualquier número (incluyendo el cero) de a’s, concatenadas a una “b” ó una “a” concatenada a cualquier numero (incluyendo el cero) de b’s . Se representa de la siguiente forma:

Q={q0, q1, q2, q3, q4}

F={q2, q3, q4}

q0=q0

S ={a, b}

Y d dada por la tabla de la figura 2.6.

Figura 2.6.

Obsérvese que en el contenido de las celdas de la tabla de transición de la figura 2.6 son conjuntos. El hecho de que existan celdas con Æ , indica que no existe ninguna transición desde el estado actual mediante la entrada correspondiente. Que para un par (estado actual, entrada) exista más de un posible estado siguiente indica que se puede elegir entre las distintas posibilidades. En el modelo no existe nada que determine la elección. Por esta razón, se dice que el comportamiento del autómata es no determinista.

Veamos otro ejemplo. Consideremos el NFA M={ Q, S , q0, F, d } que acepta el lenguaje formado por cadenas que tienen cero o más ocurrencias de “ab” ó “aba” y esta dado por:

Q={q0, q1, q2} S ={a, b}

q0=q0 F={q0}

Figura 2.7.

Y d dada por la tabla de la figura 2.7. Este NFA tiene el correspondiente diagrama de transición que se muestra en la figura 2.8.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad