Autómatas: Esos pequeños demonios

ApuntesDe

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
Captura de pantalla 2017-02-21 a las 9.07.26 a.m..png

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:

Captura de pantalla 2017-02-21 a las 9.38.52 a.m..png

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.

automata.png

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.)

turing

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:

captura-de-pantalla-2017-03-02-a-las-5-32-02-p-m

  • 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:

captura-de-pantalla-2017-02-27-a-las-5-15-08-p-m

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:

captura-de-pantalla-2017-03-02-a-las-5-16-45-p-m

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?

diagrams2

diagrams1

Partes:

captura-de-pantalla-2017-03-02-a-las-5-32-02-p-m

  • 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)
captura-de-pantalla-2017-03-02-a-las-5-33-15-p-m

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”.

captura-de-pantalla-2017-03-02-a-las-5-33-20-p-m

Lenguaje

Podemos definir de forma “formal” a un lenguaje de un NDA:

captura-de-pantalla-2017-03-02-a-las-5-35-44-p-m

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.

Captura de pantalla 2017-03-06 a las 1.54.09 p.m..png

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:

Captura de pantalla 2017-03-06 a las 1.54.41 p.m.

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:

Captura de pantalla 2017-03-06 a las 1.55.05 p.m.

Diagrama de un Deterministico

¡Y listo!

Ejemplo 2:

El pase de diapositivas requiere JavaScript.

 

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”

Captura de pantalla 2017-03-15 a las 8.05.37 p.m.

Cerradura Epsilon

Como siempre, hay que hacer nuestra tabla, pero también hay que contar a epsilon:

 Captura de pantalla 2017-03-16 a las 9.03.51 a.m.

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:

Captura de pantalla 2017-03-16 a las 9.12.01 a.m.

Para poder quitarle los epsilon, tenemos que empezar en q0, mas bien tenemos que empezar en la cerradura de epsilon de cada elemento:

Captura de pantalla 2017-03-16 a las 9.20.25 a.m..png

Veamos una de mis tareas a ver si deja las cosas más claras:

Documento de e-NFA

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 )

Google+ photo

Estás comentando usando tu cuenta de Google+. 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 )

Conectando a %s