AFD en Python - Automata finito determinista

¿Autómata?

Ex Machina

Seguramente habrás oído alguna vez esta palabra, consiente o inconscientemente puesto que en el mundo de las ciencias de la computación o del cine en ciencia ficción se habla mucho del tema, basta con que veas la reciente película llamada "ex machina", ahí hacen mención de este tema http://exmachina-movie.com/ , y día a día interactúas con ella también consiente o inconscientemente.

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.

Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados unos determinados estados y símbolos.

La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del
autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.

Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si éste termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

¿Pero en que puedo usar un autómata?

Alan Turing

Realmente los autómatas  son modelos de computadoras y su creador Alan Turing padre de la computación, desde hace años (30) estudió una maquina abstracta que poseía la misma capacidad de las computadoras actuales. Su objetivo era determinar la frontera entre lo que puede y no puede hacer una computadora, y aun cuando sus estudios están basados en estas maquinas abstractas son aplicables hoy en día a nuestros PCs.

Es una de las bases de la inteligencia artificial, los autómatas suponen un estudio más avanzado para la creación de la misma, otro gran ejemplo es en la industria, en cualquier sistema de gestión tecnológica puesto que poseen un grado de inteligencia para hacer las cosas, en centros de investigación para la búsqueda de patrones, la cual fue una de las principales causas de su creación ya que Turing previo la pérdida de tiempo al usar recurso humano para hacer búsquedas exhaustivas y fue así que surgió la creación de los autómatas. Pero si aún no queda claro, un claro ejemplo de un autómata es cuando interactúas con una computadora, en cualquier juego tu contra la computadora, más especifico en un juego de ajedrez puesto que es en si tu contra un autómata programado.

Autómata Programado

Si bien en esta entrada no crearemos una inteligencia artificial, si crearemos las bases, en esta sección avanzaremos y veremos cómo crear un autómata finito determinista en Python.

La definición formal de un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.

En este ejemplo validaremos una expresión aritmética ejemplo 12+3 o tal vez 23*3/5-8+1, sea cual sea la expresión nuestro autómata será capaz de decidir si es o no una expresión aritmética, para ello hay que crear todo desde cero.

Paso 1: Es crear nuestro autómata. Para este ejemplo propongo lo siguiente:

Dígito = + - / *         Operador = 0 1 2 3 4 5 6 7 8 9

Paso 2: Formalmente se define como una tupla (Q, Σ, q0, δ, F) donde:

 Paso 3: Ahora podemos construir nuestra tabla de transiciones:

La función del autómata será leer la cadena ingresada y dependiendo el carácter leído avanzara por los estados. Por ejemplo si ingresamos esta cadena = 34*5, el autómata comienza en el estado 0, leerá el primer alfabeto "3" y vera que el "3" es un dígito y avanzara al estado 1, comenzará a leer el siguiente alfabeto que es un "4", ahora el autómata está en el estado 1, lee el "4" y como es un dígito se mantiene en el estado 1, lee el tercer alfabeto "*" ahora el autómata continua en el estado 1, lee que es un "*" y como es un operador avanza al estado 2, continua leyendo el siguiente alfabeto "5", ahora el autómata está en el estado 2, lee que es "5" y como es un dígito avanza al estado 3, ahora esta en estado 3, continua leyendo y recibe un fin de cadena y valora si 3 es un estado de aceptación, si lo es, manda aceptación como cadena valida.

Ya con esto en mano podemos hacer uso de nuestro lenguaje por excelencia. Este código fue realizado en Python 3.

#!/usr/bin/python
# -*- coding: utf-8 -*-

# www.pythondiario.com

import re

#Definimos la funcion caracter 
def caracter(character):
    global simbolo
    simbolo=""
    global Fin
    Fin=""
    digito="[0-9]"
    operador="(+|-|*|/)"
    
    #comparamos si es digito o operador
    if(re.match(digito,character)):
        simbolo=" Digito "
        return 0
    else:
        if(re.match(operador,character)):
            simbolo="Operador"
            return 1
        else:
            if(character==Fin):
                return 2
        
        #si no es ni un digito ni un operador entonces es un caracter no validp
        print("Error el ",character,"no es valido")
        exit()

#definimos al la funcion  encabezado
def encabezado():
    print("""|  Edo. Actual |Caracter |  Simbolo  |Edo. Siguiente |""")
    body()

#definimos la funcion contenido donde guarda cada valor despues de encontrarlo en un ciclo
def contenido(estadosig,character,simbolo,estado):
    print("|     ",estadosig,"      |  ",character,"    |",simbolo," |     ",estado,"       |")
    body()

#solo muestra la linea que se repetira cada vez que la mandemos a llamar
def body():
    print("+--------------+---------+-----------+---------------+")

#MAIN
#Este es la tabla de transiciones del automata AFD creado
tabla=[[1,"E","E"],[1,2,"E"],[3,"E","E"],[3,2,"A"]]
estado = 0

print ("""+-------------------------------------+
|    Ingrese una cadena a evaluar:    |
+-------------------------------------+""")
cadena = input()
body()
encabezado()

#ciclo para recorrer la cadena
for  character in cadena:
    estadosig=estado
    
    #llamamos al metodo para saber si es un caracter valido y el valor retornado se guarda en charcaracter
    charcaracter= caracter(character)
    
    #guardamos en estado el valor obtenido en la tabla segun las cordenadas que recibio anteriormente
    estado=tabla[estado][charcaracter]
    
    #Si el valor obtenido es una E imprimimos cadena no valida
    if (estado=="E"):
        print("|     ",estadosig,"      |  ",character,"    |",simbolo," |     ",estado,"       |")
        body()
        print("""|              Cadena No Valida :(                   |
+----------------------------------------------------+""")
        exit()
    contenido(estadosig,character,simbolo,estado)

#al concluir si el estado no es 3 que es el de aceptacion imprimimos cadena no valida    
if(estado!=3):
        print("""|              Cadena No Valida :(                   |
+----------------------------------------------------+""")

#si el estado es 3 es una cadena de aceptacion
if(estado==3):
    print("|     ",estado,"      |         |    FND    |               |")
    body()
    print("""|                Cadena Valida :)                    |
+----------------------------------------------------+""")

Validación de Cadenas

Heder Ithamar Romero

Autor: Heder Ithamar Romero

Seguir en Google +