Autómatas Finitos

 

Un autómata es una máquina matemática M formada por 5 elementos M = (Σ, Q, s, F, δ) donde Σ es un alfabeto de entrada, Q es un conjunto finito de estados, s es el estado inicial, F es un conjunto de estados finales o de aceptación y δ (delta) es una relación de transición.

Símbolo: es un signo que representa algo abstracto. En este material, símbolo se referirá a un carácter alfanumérico.

Ejemplos: a, b, 1, 0, x, y, z, 9,

Alfabeto: es un conjunto de símbolos y normalmente se denota con la letra Σ. 

Cadena: o palabra es un conjunto de símbolos de algún alfabeto Σ concatenados entre sí, es decir uno enseguida del otro. 

Ejemplos: 

• Para el alfabeto Σ = {a,b,c,…z} algunas cadenas son: ab, z, cc, abc, abab 

• Para el alfabeto Σ = {0,1} algunas cadenas son: 0, 1, 01, 000, 0101

Cadena Vacía ε: es la cadena que no contiene ningún símbolo. Lenguaje es un conjunto de cadenas o palabras definido en un alfabeto Σ. 

Ejemplo: Si Σ = {0,1} podríamos definir los lenguajes “conjunto de cadenas en Σ que terminan en 0” algunos de las palabras del lenguaje serían: 0, 10,00,010,100, 110…

Ejemplo:

Ejemplo 1

Autómatas finitos deterministas

Un autómata finito determinista AFD es un caso particular de los autómatas finitos, en el que la función de transición no presenta ninguna ambigüedad en las transiciones de estados para una entrada dada. Un autómata finito determinista es una quíntupla AFD=(E, Q, f, q1, F) donde la función es determinista.

Ejemplo 2

Definición del AFD

Este tipo de autómatas admite su definición de dos maneras bien diferentes: Como autómatas traductores o reconocedores. La definición como autómatas traductores continúa a la definición de las máquinas secuenciales, y se los podría definir como una subclase de estas, ya que los autómatas finitos tendrían como limitante no poder iniciar desde cualquier estado como lo hacen en las máquinas secuenciales.

Ejemplo 3

La forma que adoptaremos para la definición de los autómatas finitos deterministas es como autómatas reconocedores, ya que se ajusta con los contenidos de la informática teórica y utilización que se les da dentro del diseño de los analizadores léxicos.

Estos autómatas solo se limitarán a aceptar o no una determinada cadena recibida en la entrada, por lo tanto, podemos decir que la salida de los mismos solo tendrá dos valores posibles aceptar o no aceptar a la palabra de entrada.

Al igual que en las máquinas secuenciales, estos autómatas transitarán entre un conjunto finito de estados posibles, a medida que reciban sucesivamente los caracteres de entrada, en un instante determinado de tiempo el autómata solo podrá estar en uno y solo uno de los estados posibles.

Una característica importante de este tipo de autómatas es el determinismo, lo cual significa que estando en un estado y recibiendo una entrada del exterior el autómata tendrá la posibilidad de transitar a uno y solo un estado del conjunto de estados posibles. 

Lenguaje reconocido

Es el conjunto de todas las palabras reconocidas por el Autómata Finito Determinista.

            L AFD = { x / x    ∑* y  f ( q0,  x) = qn con qn    F }

Ejemplo:

             Dado el siguiente AFD definido como: AFD1 = ( ∑, Q, qi, F, f ), donde:

∑= { 0,1 } (Conjunto de símbolos de entrada del AFD)

Q= { p, q, r } (Conjunto de estados del AFD) 

qi = p  (estado inicial del AFD  (p Є Q))

F= {q } (Conjunto de estados de aceptación del AFD  ({q } с  Q))

f: función de transición de estados del AFD 

También puede expresarse como
f(p,0) = q	f(p,1) = r
f(q,0) = p	f(q,1) = q
f(r,0) = r	f(r,1) = r

Donde la función f será:

	f	0	1
→	p	q	r
*	q	r	q
	r	r	r

Ejemplo 4

Aplicación

Dentro de los usos que se le pueden dar a las máquinas de estados, y en particular a los AFD, está el reconocimiento de cadenas. Para realizar este reconocimiento en forma precisa y automatizada, el mismo puede implementarse en cualquier lenguaje de programación. Será posible que habiendo diseñado un autómata que sea capaz de reconocer un conjunto de cadenas de un lenguaje, construir un programa que implemente dicho autómata en algún lenguaje de programación, a tal fin el Algoritmo de funcionamiento del programa puede ser obtenido a partir del AFD en forma directa. Ejemplo:

AFD5 = ( {0,1}, {p,q,r,s,t}, p, {q}, f ) Donde la función f :

	f	0	1
→	p	s	t
*	q	q	t
	r	q	t
	s	s	r
	t	t	t

Y su forma gráfica es:

Ejemplo 5

El lenguaje aceptado por este autómata es: L AFD5 = { x / x W(Σ) / an.b.am con n,m 1 }

Equivalencia entre un DFA y un NFA

Un NFA es normalmente más fácil de definir, aunque al mismo tiempo, para cualquier NFA N existe un DFA D tal que L(D) = L(N) y viceversa. Para esto se usa la construcción de subconjunto que muestra un ejemplo de cómo un autómata se puede construir a partir de otro. Para cada NFA existe un DFA equivalente (acepta el mismo lenguaje). Pero el DFA puede tener un numero exponencial de estados.

Sea N = (QN, Σ, δN, q0, FN) un NFA. El DFA equivalente construido a partir del subconjunto de construcción es : D = (QD, Σ, δD, {q0}, FD), donde: • |QD| = 2 |QN | ; i.e., QD es el conjunto de todos los subconjuntos de QN. • FD es el conjunto de conjuntos S en QD tal que S ∩ FN 6= ∅. • Para cualquier S ⊆ QN y a ∈ Σ, δD(S, a) = S p∈S δN(p, a), ósea, la unión de todos los estados a partir de p con entrada a. δD({q1, q2, . . . , qk }, a) = δN(p1, a) ∪ δN(p2, a) ∪ . . . ∪ δN(pk ,a). La función de transición δD del NFA anterior es:

Ejemplo 6

Al existir 3 estados, tenemos 8 subconjuntos. Esto mismo lo podemos poner como:

Ejemplo 7

Lo cual es un DFA (simplemente cambiando la notación). También es importante notar que no todos los estados pueden ser alcanzados. En particular, solo los estados B, E y F son accesibles, por lo que los demás los podemos eliminar. 

Una forma de no construir todos los subconjuntos para después encontrar que solo unos cuantos son accesibles, es construir la tabla solo para los estados accesibles (lazy evaluation). En notación y forma gráfica tendríamos:

Ejemplo 8

Finalmente, dejamos un video donde se explican estos conceptos.

Nota: El video es usado con fines educativos. Todos los derechos pertenecen al autor.

Bibliografía:

• Cueva Lovelle, J. M., Izquierdo Castanedo, R., Juan Fuente, A. A., Ortin Soler , F., & Labra Gallo, J. E. (Noviembre,2003). Lenjuages, Gramatica y automatas en Procesadores de Lenguaje. Oviedo: SERVITEC.
• GHD. (2006). Obtenido de https://www.institucional.frc.utn.edu.ar/sistemas/ghd/T-M-AFD.htm Jurado, E. (2008). Teorias DE Automatas y Lenjuages Formales. Caceres, España: Universidad de Extremadura.
• Toche, L. O. (Marzo de 2017). uaemex. Obtenido de: http://ri.uaemex.mx/bitstream/handle/20.500.11799/70527/secme-7617_1.pdf

Ecribió: Max Huerta Camarena.

Editó: Rodrigo R. Rubio Haro.