resumen ejecutivo AFN

Integrantes:

Armijo Oyarzun Carlos Eduardo
Guiñez Acuña Rodrigo Fernando
Ziegler Angulo Manfred Werner

Objetivo:

Exponer los conceptos que caracterizan a los Autómatas Finitos No Deterministas (AFN), su notación, funcionamiento, los lenguajes que acepta, las diferencias con los Autómatas Finitos Deterministas (AFD) y los pasos para construir un AFD a partir de un AFN.

Desarrollo del tema:

Los autómatas son máquinas conceptuales para el reconocimiento de patrones. Son una representación matemática de un sistema que recibe una cadena de símbolos pertenecientes a un alfabeto determinado y determina si esa cadena es aceptada o no (si pertenece al lenguaje que reconoce el autómata).

Un Autómata Finito No Determinista (AFN) se define como una quíntupla de la siguiente manera:

A=(Q,T,λ,q0,F) donde :

Q = Conjunto finito y no vacío de estados,

T = Alfabeto de entrada,

λ = Función de transición que toma como argumentos un estado de Q y un símbolo de T, y devuelve un subconjunto de estados de Q.

q0 = Subconjunto de Q que representa al conjunto de estados iniciales (a diferencia de los AFD, los AFN pueden admitir varios estados iniciales).

F = Subconjunto de Q que representa al conjunto de estados de aceptación (estados finales).

Los Autómatas Finitos No Deterministas, también llamados AFN, se caracterizan porque, a diferencia de los AFD, en un estado puede haber más de una transición posible para un mismo símbolo de entrada (alfabeto). Es decir /λ(q,a)/ ≥ 1 para algún "q" perteneciente a Q y para algún símbolo "a" perteneciente a T.

Ejemplo : Según el siguiente autómata :





Donde λ (q0,01)=λ(λ(q0,0),1)=λ({q0,q1},1)={q0,q1}.

Otra diferencia importante de los AFN con respecto a los AFD es la posibilidad de tener más de un estado inicial.


El lenguaje aceptado por un AFN es el conjunto de cadenas tales que después de ser analizadas, el AFN ha logrado alcanzar al menos un estado de aceptación. Tales lenguajes de definen de la siguiente manera :

L(A) = {x perteneciente a T*/ λ(q0,x) intersección F≠ Ø}.

Es importante establecer que para un lenguaje L aceptado por un AFN, entonces existe un AFD que también acepta el lenguaje L. Es por esto que se hace posible, a partir de un AFN diseñar un AFD equivalente.

La operación de calcular un AFD a partir de un AFN es muy común y , por ello, se han desarrollado métodos para hacerlo. El más sencillo y eficiente es el siguiente :

1.- Se construye una tabla en la que cada columna está etiquetada con un símbolo del alfabeto de entrada y cada fila se etiqueta con un conjunto de estados.

2.- La primera fila se etiqueta con {q0}, y en cada entrada de la tabla se ponen los conjuntos de estados (P) a los que llevan lo símbolo correspondiente a la columna.

3.- Se etiqueta cada fila con cada uno de los conjuntos P que no tengan asociada una fila en la tabla (es decir, cada uno de los conjuntos P que aparezcan por primera ves en la tabla) y se completa cada una de estas filas con los correspondientes conjuntos de estados (P) a los que llevan los símbolos de cada columna.

4.- Se realiza el paso tres hasta que no hayan conjunto P sin filas asociadas.

5.- Se asocia a cada conjunto P que aparezca en la tabla un estado en el nuevo AFD y aquellos que tengan entre sus componentes algún estado final del AFN se considerarán estados finales en el AFD.

Ejemplo:
Para el siguiente AFN:




AFD resultante:


Conclusión:

Los Autómatas Finitos No Deterministas son modelos matemáticos que permiten representar situaciones complejas de una manera más directa, pero a la vez más difícil de predecir, debido a que pueden estar en varios estados de manera simultanea, esto hace muy valioso tener un método para transformar un AFN en AFD, para así obtener resultados más manejables.