La teoría de los autómatas es el estudio de las maquinas «abstractas» de la computación, su objetivo es describir como es que una computadora analiza la información (ignorando la molesta parte física y concentrándonos en la lógica).
Los autómatas son como podemos aplicar las máquinas de Turing en la vida real, son un modelo computacional, es decir, no «son código», son ideas, ideas abstractas que nos permite solucionar problemas.
Características:
- Es una máquina de estados finitos, es decir, no puede tener una cantidad infinita de estados.
- Es ahistórico, es decir, no tiene memoria, no puede guardar nada. Siempre se enfoca en el presente.
Funcionamiento
Un autómata recibe un string, un string de un alfabeto conocido, en general el binario o el ASCII y lo va leyendo un carácter a la vez, nuestro autómata esta hecho de «estados», empezamos en uno (generalmente lo llamamos q0) y dependiendo de que carácter veamos, iremos a otro estado, y así consecutivamente hasta que lleguemos al final de la cadena, cuando llegue este momento, veremos si nuestro estado actual es el final.
Diagramas
Para poder dibujar estos autómatas de manera mas cómoda hemos llegado a un acuerdo sobre cómo podemos dibujarlo.
Todo autómata de estas características, se puede dibujar con las siguientes características:
- Un círculo que representa un estado
- Unas flechas que representan a qué estado se tiene que ir dependiendo de qué caracter lee en este momento
Puedo tener «bucles»
También cada autómata tiene que tener un estado inicial, generalmente a menos que se nos diga otra cosa es el q0:
El autómata siempre empieza en q0
Y también tiene un estado (o más de un uno) que son estados finales, es decir que nos importará cuando termines la cadena, estos son los círculos que tienen un circulo dentro.
El estado inicial también puede ser la final también
Crear Diagramas Online
Ejemplos:
Paridad
Por ejemplo el autómata que ve si la cadena tiene paridad de cero y uno (osea que la cantidad de ceros y la cantidad de unos es par.)
La Función de Transición
Podemos describir de gran manera como es que se comporta un autómata por su función de transición, esta son las flechas, toma como entrada un estado y un carácter o símbolo y regresa un nuevo estado al que hay que dirigirse.
Hablaremos más de esta función al ver lo tipos de Automátas, pero quería que supieras que existe.
Representación
Como vimos, hay dos formas generales de representarlo, ya sea un diagrama o una tabla de estado:
Si nos queremos poner muy formales, vamos a ver como los podemos clasificar:
DFA
Autómatas Finitos Deterministico
Aquí la palabra clave es DETERMINISTICO.
Eso quiere decir, que sin importar si lo corremos una vez o mil, si lo hacemos de día o de noche, siempre saldrá el mismo resultado ,es más eso, quiere decir que el azar no entra en ningún lado, que un estado solo puede tener un camino por símbolo.
Repito: Que un estado SOLO puede salir a otro por cada posibilidad. Es decir, que por ejemplo para el estado q3 solo puede haber una flecha que te indique a donde ir si vez un 1.
Partes:
- Un conjunto finito de estados (Q)
- Un conjunto finito de entrada (Σ)
- Una Función de Transición (Delta, no se como escribir eso es ASCII)
- Un estado inicial que pertenezca a Q (qo)
- Un subconjunto de Q que llamamos estados finales (F)
Además podemos definir el lenguaje de unos de estos autómatas como:
Lenguaje
Podemos definir de forma «formal» al lenguaje de uno de estos Automátas como aquel conjunto de strings que cumple con la siguiente expresión:
Es decir, en español: Son todos los string que cuando los pasamos por un autómata finito determinado ( o DFA ) que cuando se le pasan por el autómata, terminan en uno de los estados finales.
Por ejemplo usando algunos autómatas muy comunes algunos Lenguajes Regulares son:
- Todos los string binarios que acaban en 01.
- Todos los strings binarios que tengan una cantidad par de ceros y unos.
Delta Gorro
Para poder «analizar» string, usamos una función extra, una que solemos llamar «delta gorro», esta es:
Función
Para analizar este automata:
NFA
Autómatas Finitos NO-Deterministico
Aquí la palabra clave es NO DETERMINISTICO.
Son casi iguales que los anteriores, pero hay algo que los hace diferentes y esa única diferencia es la clave, pueden estar varios lugares a la vez.
Esto es porque tiene varios caminos para una misma entrada.
¿Qué?
Pues que basicamente a mi forma de verlo es como la física y la cuántica, cuando nuestro autómata se enfrenta a la decisión, cuando tiene delante dos camino igual de validos, lo que nosotros hacemos es crear dos «universos» uno donde se va por ejemplo por la derecha y otro donde se va a la izquierda, un universo donde va a a q0 y otro donde va a q3 por ejemplo, veamos un diagrama de estas cositas.
¿Qué hace este autómata cuando ve un 0 y esta en q0?
Partes:
- Un conjunto finito de estados (Q)
- Un conjunto finito de entrada (Σ)
- Una Función de Transición (Delta, no se como escribir eso es ASCII)
- Un estado inicial que pertenezca a Q (qo)
- Un subconjunto de Q que llamamos estados finales (F)
y tiene su tableta también
Delta Gorro
Es en Delta Gorro donde encontramos las mayores diferencias, pues NO regresa un estado, sino un conjunto, un conjunto de todos los posibles estados, un conjunto de todos los posibles «universos».
Lenguaje
Podemos definir de forma «formal» a un lenguaje de un NDA:
Es decir, en español: Son todos los string que cuando los pasamos por un autómata finito NO determinado ( o NFA ) que cuando se le pasan por el autómata, me regresan un conjunto donde AL MENOS uno de sus miembro pertenece a uno de los estados finales.
(O aun más formal: Que entre nuestro conjunto de estados que sale de evaluar w, al hacerle la intersección con el conjunto de los estados finales encontramos que no es nula, es decir, existen estados que estan en nuestro conjunto y que al mismo tiempo son estados finales).
De NFA a DFA
Supongamos el siguiente autómata que se encarga de aceptar cualquier cadena que acabe en 0,1.
Para pasarlo a un Autómata determinada, primero tenemos que hacer una tabla, donde estén: Cada Elemento del Conjunto Potencia, es decir: cada posible subconjunto de todo los estados del autómata, como la siguiente:
Conjunto Potencia
Una vez, listo, podemos hacer una tabla de que pasa a cada subconjunto si ve cada elemento:
Recuerda que la flecha señala al estado inicial y los asteriscos a los estados finales:
(También podemos pasarlo a letras si te es mas cómodo para no escribir tanto)
Ahora lo que hacemos es iniciar por el estado inicial y ver a cuales subconjuntos nos podemos mover hasta llegar al final o a un ciclo.
Gracias a esto podemos dibujarlo:
Diagrama de un Deterministico
¡Y listo!
Ejemplo 2:
Veamos una de mis tareas a ver si deja las cosas más claras:
Documento de NFA
ε-NFA
Transiciones Epsilon
Añadiremos una nueva característica a nuestro autómata, la que nos permita que lea «nada» literalmente que nos permita no leer nada. Una cadena vacía. Epsilon.
Es más puedes imaginar que nuestra cadena tiene una cantidad necesaria de epsilon dentro de la misma cadena.
Veamos la utilidad en todo esto:
Podemos desarrollar un autómata que se encarga de aceptar decimales, estos consisten en :
- Un «+» o «–» opcional
- Una cadena de decimales
- Un punto decimal
- Una cadena (otra) de decimales
Es totalmente posible que una de las dos cadenas este vacía, pero obvio no las dos.
Por ejemplo:
- «1.0»
- «32.»
- «-.2323»
Cerradura Epsilon
Como siempre, hay que hacer nuestra tabla, pero también hay que contar a epsilon:
En la columna de epsilon va lo que se conoce como la cerradura de epsilon, es decir, es la que nos dice a donde podemos ir solo moviéndonos entre caracteres varios.
Es decir:
Para poder quitarle los epsilon, tenemos que empezar en q0, mas bien tenemos que empezar en la cerradura de epsilon de cada elemento:
Veamos una de mis tareas a ver si deja las cosas más claras:
Compilando Conocimiento 