Python R2


Jugando con Automatas en Python (AFN -> AFD)


Después de tanto tiempo de no escribir y ya preparando la charla para dar en la FLISOL de  Carmelo me puse a jugar un poco con autómatas (Talvez muestre algo de esto allá). Este script lo que hace es bastante simple transforma un autómata finito no determinista a un autómata finito determinista. 😉 Saludos y espero que les guste.

#!/usr/bin/python
# Clase AFN para transformar un AFN en un AFD

class AFN:
    def __init__(self,AFN):
        self.AFN = AFN
        self.SimbolosDelLenguaje =  self.LenguajeDeAFN()
        self.AFD = self.ToAFD()
    def Transaccion(self,e,t):
        return filter(lambda s:s[0]==t,filter(lambda s:s[0]==e,self.AFN)[0])[0][1]

    def EstadoInicial(self):
        # retorna una lista con el unico estado inicial
        return filter(lambda s:len(s)>=4 and s[3]=='>',self.AFN) #simpre tendria que ser uno por definicion de automatas

    def LenguajeDeAFN(self):
        # simbolos del lenguaje del AFN
        return [l[0] for l in  filter(lambda s:len(s)==2,self.AFN[-1])];

    def EstadosTratados(self):
        return [e[0] for e in  self.AFD] # los estados de llegada que fueron tratados

    def EstadosNoTratados(self):
        return map(lambda e:e[1],filter(lambda s:s[0] in self.SimbolosDelLenguaje and s[1] not in self.EstadosTratados(),self.AFD[-1]))

    def ToAFD(self):
        self.AFD =[]
        vecEstTmp= self.EstadoInicial()

        while len(vecEstTmp) <> 0:
            self.AFD.append( vecEstTmp[0])
            for estado in self.EstadosNoTratados(): #se recorren todos los estados que no fueron tratados
                TransaccionDelAFD=[] #en este vector se calculara los  las transacciones del AFD resultantes
                for simbolo in self.SimbolosDelLenguaje: # recorro para todos los simbolos del lenguaje
                    nuevoEstado=[]                       # defino nuevoEstado para armar el nuevo estado del AFD
                    for e in estado:                     # calculo la union con los conjuntos de llegada de todos los estados
                        for t in self.Transaccion([e],simbolo):
                            if t not in nuevoEstado:
                                nuevoEstado.append(t)
                        nuevoEstado.sort()

                    TransaccionDelAFD.append([simbolo,nuevoEstado])

                vecEstTmp.append([estado]+TransaccionDelAFD)

            vecEstTmp.pop(0)

        #busco los estados de Aceptacion y le pongo el *
        estasdosDeAceptacion = [l[0][0] for l in filter(lambda s:len(s)>=4 and s[-1]=='*',self.AFN)] #estados de Aceptacion
        for e in self.AFD:
            Aceptacion = False
            for ea in estasdosDeAceptacion :
                        if not Aceptacion:
                            Aceptacion =  ea in e[0]
            if Aceptacion and '*' not in e: e.append('*')

        return self.AFD

AUT = AFN(
        [
        [ [1], ['a',[1]] ,['b',[1,2]],'>'],
        [ [2], ['a',[] ] ,['b',[3]  ]],
        [ [3], ['a',[3]] ,['b',[3]  ],'*']
        ]#tabla de trancicion marcando con una -> el estado inicial y con * los estados favorables
        )

for l in  AUT.AFD:
    print l
Anuncios

15 comentarios to 'Jugando con Automatas en Python (AFN -> AFD)'

Subscribe to comments with RSS o TrackBack to 'Jugando con Automatas en Python (AFN -> AFD)'.

  1. tabris said,

    mmmm muy interasante eh

  2. Tordek said,

    Te pongo unas quejas:

    1) No podés tener una ‘clase que transforma’. Tenés una clase que representa, y esa clase contiene un método que transforma.
    2) “self.AFD” medio que sobra; no es necesario cachear el resultado por el usuario; si tuvieras una clase que representa un AFN, y contiene, además, un metodo “to_AFD”, podrías agregar estados o transiciones a voluntad.
    3) Preferiría que el generador ADF tomara 4 parámetros, para que tenga una forma más parecida a la definición de Autómata: una lista con los nombres de estados, una lista de estados iniciales, una lista de estados finales, y una lista de transiciones, cada una representada por (estado de origen, caracter, estado final).
    Compará esta sintaxis para la creación:

    AFN(['1','2','3'],
        ['1'],
        ['3'],
        [('1', 'a', '1'),
         ('1', 'b', '1'),
         ('1', 'b', '2'),
         ('2', 'b', '3'),
         ('3', 'a', '3'),
         ('3', 'b', '3')])

    Es más larga, pero es más natural para representarlo “como un matemático”.
    4) Un AFN puede tener todos los estados iniciales que quiera.
    5) PEP-8. En serio. Es lindo.

  3. Tordek said,

    (Bah, en realidad, ahora que mandé, me parece que lo mejor es no poner como string los nombres, sino como números; pero, todo es discutible.)

  4. Tordek said,

    Bah, pensando un poquito se puede discutir una de dos cosas:

    1) Si va la lista de estados, debería ir el alfabeto de entrada (que es la opción más correcta, matemáticamente hablando)
    2) Si _no_ va el alfabeto, tampoco debería ir la lista de estados, dado que se pueden deducir ambas a partir de la lista de transiciones.

    Creo que me quedo con la 2da, que si bien hace más trabajo al programador, hace menos al usuario.

  5. Arturo Elias Anton said,

    jejej Hola Tordek es verdad tendría que leer el PEP-8.
    Soy yo o tuviste una noche difícil de conciliar el sueño 😉
    Bueno como siempre Gracias por tus consejos ya que sos uno de los usuarios con los que mas e discutido mis Script.
    El único detalle a comentarte es que si lo que queres es representarlo “Matemáticamente Hablando” decir una lista de estados iniciales esta mal ya que los estados iniciales siempre son únicos. Así que si se hace de forma matemática se tendría que definir como único elemento. Y no esperar una lista.

    Saludos y sigo esperando mas sugerencias!!!!!!!!!!

  6. Tordek said,

    En un AFD tenés un sólo estado inicial, y uno sólo final; en un AFN tenés todos los iniciales y finales que quieras. Eso fue lo que me enseñaron a mi en la UTN.

    Google dice “Algunos textos permiten que hayan varios estados iniciales”.

    Matemáticamente, son equivalentes: Está demostrado que un AFN con transiciones epsilon(o lambda, como sea que diga la literatura) es equivalente a uno sin ellas. A partir de eso, podemos armar un AFN con un varios estados iniciales, y éste sería equivalente a uno con un sólo estado inicial, con transacciones lambda entre el estado inicial, y los otros estados que hubiéramos marcado como iniciales.

    Equivalentemente, se puede decir que sólo necesitás un estado final—lo único que necesitás es que todos tus estados de aceptación tengan una transición lambda a qA.

  7. Tordek said,

    Epa. En un AFD tenés todos los finales que quieras.

  8. Arturo Elias Anton said,

    Tordek mira la verdad es que un AFN con múltiples estados iniciales no entra en la definición de AFN ya que la definición matemática de un AFN en (Q,S,fx,q0,F)

    Donde Q es el conjunto de estados del autómata.
    S es el conjunto finito de simbolos de entrada.
    fx es la relación de transición.
    q0 que es el estado inicial y pertenece a el conjunto Q. (por este motivo digo que no puede ser varios estados ya que esto tendría que ser un conjunto).
    F un conjunto de estados incluido en Q que representan los estados finales.

    Si puede ser que exista una estructura nueva llamada X que sea (Q,S,fx,Q0,F) que es igual pero Q0 esta incluida en Q y representa todos sus estados iniciales. Y para llevarla a un AFD haya que trasformarla en un AFD-e. Pero no cumpliría estrictamente con la definición de AFN así que mi opinión es que no es un AFN

    La definición de AFN se puede sacar del libro “Introducción a la teoría de Autómatas, lenguajes y computación Autores Hopcroft, Motwani, Ulllman ISBN 84-782-9056-7 pagina 63“

    • matias said,

      (por este motivo digo que no puede ser varios estados ya que esto tendría que ser un conjunto).
      se puede confirmar con la el Método de ecuaciones lineales y con el Método recursivo van representados respectivamente-
      EJ: Método de ecuaciones lineales

      X1=X1 0+E en el caso que el estado 1 sea inicial ->
      X2=………. determinado dependiendo del diagrama de estados.
      X3=………..determinado dependiendo del diagrama de estados

      X1=nodo inicial, en todo los casos el nodo incial puede variar X1,X2,X3 etc pero siempre es un solo estado inicial por la def del conjunto Q que explica Arturo.
      E=palabra vacía

      determinando el estado inicial + E, así formaras el sistema de Ecuaciones empiezas a resolver aplicando Arden y propiedades básicas

      AF->ER Def.

      agradecimiento a la profesora de PLF JACQUELINE KÖHLER
      espero le aclare la duda sobre estado inical de un automata finito

  9. Tordek said,

    Googleá por “finite automata “initial states””. Encontrás cientos de resultados que hablan de autómatas con múltiples estados iniciales. La definición depende del libro en que leas; así como algunos dicen que sólo podés tener un estado inicial, algunos le dicen a la cadena nula “lambda” y otros “epsilon”…

    Pero, bueno, si tu mundo se basa en un sólo libro, como lo prefieras; un AFN con múltiples estados iniciales se puede transformar a uno con uno sólo.

  10. Julian said,

    Tordek, no creo que una persona en su sano juicio trate de resumir el “mundo” de automatas en un solo libro ni mucho menos en un blog. Claramente no es la idea. Muy buena implementacion Arturo!.

  11. arzak9 said,

    buena implementación(perdón, el python no incluye acentos XD), en realidad soy ingeniero electrónico y me puse a programar, esperando hacer una implementación de autómatas finitos , pero creo que con la teoría que estudié , la implementación sería mucho más sencilla(tener en cuenta que los robots tienen un procesador parecidos a los atari), consejo, estudien diseño de automatas, con todo eso de karnaugh, y las escalerita etc. referencia(no la unica, tocci, digital …no me acuerdo, capitulo 5 es facil de encontrar), chao y saludos son muy buenos en la programación

  12. Gio said,

    Alguien tien algun codigo en php o en java, para convertir un afn a afd

    • Arturo Elias Antón said,

      Ya esta arreglado


Responder

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


A %d blogueros les gusta esto: