Autómatas finitos no deterministas

En esta página vamos a explicar el funcionamiento y como realizan las transacciones los autómatas finitos no deterministas, anteriormente hemos explicado que son y como actuan los autómatas finitos deterministas.

Definición de Autómata finito no determinista (AFND)

Definición de AFND (son equivalentes):

1.AFND = (Σ,Q, f,q0,F), donde

      •f: Q x (Σ U λ}Q es No determinista, es decir, por ejemplo: f(p,a) = {q,r} y f(p,λ) = {q,r}

2.AFND = (Σ,Q, f,q0,F, T), donde: ,Q, q0,F : idemque en AFD. Y además:

      •f : Q xΣ -> P(Q): conjunto de las partes de Q
•T : Relación definida sobre pares de elementos de Q.

pTq= (p,q) T si está definida la transición f(p,λ )=q
Nota: “T” es la definición formal de la transición

Peculariedades de Autómata finito no determinista (AFND)

Peculiaridades:
1. No determinismo.
2. Transiciones No definidas.
3. Posibilidadde transitar de estado, aún sin leer ningún símbolo de entrada.

Ejemplo de Autómata finito no determinista (AFND)

Autómatas finitos no deterministas (AFND), función de transición extendida a palabras

Calculo de T*. Método de la matriz de pares de estados

  • Se construye una matriz con tantas filas como estados.
  • En la 1ª columna se coloca el par correspondiente al estado en cuestión, es decir, por ej. (p,p) puesto que cada estado es accesible desde si mismo.
  • En las columnas siguientes se añaden las transiciones definidas en el Autómata finito no determinista , considerando si el hecho de añadirlas permite extender alguna transición más.

                   – Por ejemplo. Si existe la transición λ(q,r) y se añade la transición (r,s), habrá que añadir asimismo, la transición (q,s).

  • Cuando no sea posible añadir ningún par más, se habrá terminado T*

Lenguaje aceptado por un autómata finito no determinista (AFND)

  • El lenguaje reconocido por un Autómata finito no determinista (AFND) puede definirse casi igual que el lenguaje reconocido por un autómata finito determinista AFD, si utilizamos la definición de función de transición sobre palabras (f’ para el AFND).
  • Sólo hay que tener en cuenta que, en el caso del AFND, al obtenerse por medio de f’ varios estados, la condición de aceptación será que alguno de dichos estados sea un estado final del autómata.
  • Una palabra x * es aceptada por un autómata finito no determinista (AFND) si: f’ (q0,x) y F tienen al menos un elemento común, es decir, que f’(q0,x) contiene al menos un estado final.
  • El conjunto de todas las palabras aceptadas por un autómata finito no determinista (AFND) es el lenguaje aceptado por ese AFND.
  • Al ser un Autómata finito no determinista AFND, desde qo puede haber más de un camino para la palabra “x ”, y “x”es aceptada sólo con que uno de los caminos lleve a un estado final.
  • Además λ pertenece a L AFND si :

-Qo Pertenece a F ó

-Existe un estado final, q pertenece a F, tal que está en relación T* con qo (qo T* q)

AFD equivalente a un AFND

  • Dado un AFND siempre es posible encontrar un AFD que reconozca el mismo lenguaje:

•El conjunto de los LAFND= al conjunto de los LAFD.
•Un AFND no es más potente que un AFD, sino que un AFD es un caso particular de AFND.

  • Paso de AFND a AFD:

•Sea el AFND A = (, Q,f,qo,F,T).
•Se define a partir de A el AFD B, donde:
B = (, Q’,f^,qo’,F’), tal que:
Q’= P(Q) conjunto de las partes de Q que incluye a Q y a Ø.
q0’ = f’(qo,) (f’ extensión a palabra de f, i.e. todos los estados que tengan relación T* con q0).

2 comentarios (+add yours?)

  1. Bienvenidos a nuestro nuevo blog « Automátas, gramáticas y lenguajes formales
    feb 29, 2012 @ 09:25:00

  2. Autómatas finitos deterministas y no deterministas « Automátas, gramáticas y lenguajes formales
    mar 26, 2012 @ 08:49:02

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: