viernes, 11 de diciembre de 2009

¡¡¡BIENVENIDOS AL BLOG DE LOS AUTÓMATAS FINITOS!!!

El objetivo de este blog es facilitar la comprensión sobre el comportamiento de los autómatas finitos. Para ello, se procederá a resaltar los aspectos y características más importantes de éstos. A continuación, se muestra un mapa conceptual que representa el contenido de esta página:



DEFINICIÓN

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
Éstos se definen mediante una quíntupla (E, Q, f, q0, F ) donde:


E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación.

CLASIFICACIÓN

Los autómatas se pueden clasificar en:


Deterministas

  • Cada combinación (estado, símbolo de entrada) produce un solo estado.

No Deterministas

  • Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

REPRESENTACIÓN

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

Tablas de transición:
• Filas encabezadas por los estados( Q )
• Columnas encabezadas por los símbolos de entrada ( E)



TABLA
ab
->pq
*qq3r
q3
r
rq3



Diagramas de transición:
• Nodos etiquetados por los estados(Q)
• Arcos entre nodos etiquetados con ( E)
• Q0 se señala con ->
• El estado final se señala con * o con doble circulo




Ejemplo: Sea el AFD1 = ({a,b}, {p,q,r}, f, p, {q}) donde f está
definida por:
f(p,a) = q f(p,b) = r
f(q,a) = q f(q,b) = r
f(r,a) = r f(r,b) = r
escribir su tabla de transición y dibujar su diagrama de transición.

estados (Q): p, q, r
estado inicial: p
estado final: q
símbolos: a,b


AFD

AFND


RECONOCEDOR DE LENGUAJE

AF como reconocedor de un Lenguaje:

• Cuando un AF transita desde q0 a un estado final en varios movimientos, se ha producido el RECONOCIMIENTO o ACEPTACIÓN de la cadena de entrada.
• Cuando un AF no es capaz de alcanzar un estado final, se dice que el AF NO RECONOCE la cadena de entrada y que ésta NO PERTENECE al lenguaje reconocido por el AF.

Ejemplo:

A partir del autómata, comprobar si reconoce la palabra “aabbaba”.


Empezaríamos en el estado P, al recibir una "a", pasaríamos a Q, al recibir una "a" de nuevo, seguiríamos en Q, después al recibir una "b", pasaríamos a R, y recibiendo otra "b", seguiríamos en R. A continuación recibiríamos una "a", que nos llevaría a R y así hasta el final. Por lo tanto al quedar después de la palabra leída en el estado R, y dado que este no es un estado final como lo es Q, la palabra no se reconocería. En cambio la palabra “aa” si que se reconocería puesto que terminaríamos en el estado final Q. Se trata por tanto de un autómata que reconoce lenguajes formados exclusivamente por una o varias “a”.

AUTÓMATAS CONEXOS

Estados accesibles y Autómatas conexos

Definición:

Sea un AFD = (E, Q, f, q0, F),
el estado p es ACCESIBLE desde q si f’(q, x) = p. En otro caso se dice que es INACCESIBLE.
Resultado: Todo estado es accesible desde sí mismo pues f’(p, λ ) = p

Por tanto, un autómata es conexo si todos los estados son accesibles desde el estado inicial. Para convertir un autómata no conexo en conexo hay que eliminar los estados no accesibles.Es importante destacar que un autómata conexo y su no conexo equivalente, reconocen el mismo lenguaje.

CONEXO



NO CONEXO

MINIMIZACIÓN

Si queremos calcular el autómata mínimo equivalente de cierto autómata, tenemos que obtener el conjunto cociente Q/E.

Para ello, asignamos clases a los diferentes estados, siendo para la primera iteración, C1( clase 1 ) para los estados finales y C2( clase 2 ) para el resto de estados.
Q/E0={ C1(p, q, r) , C2(s, t, u, v)}




Posteriormente analizando la nueva tabla de transiciones, comprobamos si se ha creado alguna clase nueva, que denominaremos como C3. En este caso el estado “s” es distinto al resto de estados de la clase 2, por lo tanto se le asignará C3 a dicho estado, pasando a ser Q/E1 = {C1(p, q, r), C2( s), C3(t, u, v)}

Q/E1
abab
*ppqC1C1
*qrpC1C1
*rrrC1C1
->stpC2C1
ttuC2C2
utvC2C2
vvuC2C2





A continuación, hemos comprobado que no se ha creado ninguna clase extra, por lo tanto, el Q/E2 será el mínimo equivalente. Para representar dicho autómata, consideraremos las clases como los estados y representaremos sus correspondientes transiciones.

Q/E2
ab
*pC1C1
*qC1C1
*rC1C1
->sC3C1
tC3C3
uC3C3
vC3C3




RECURSOS

Los recursos que os pueden servir para profundizar en el tema, constan de libros en formato electrónico, de libros disponibles en el catálogo de las bibliotecas y de revistas científicas.

LIBROS ELECTRÓNICOS

Yannis Haralambous “Fonts & Encodings”, O'Reilly Media, Inc., (2007)
Disponible en safari.

LIBROS

• Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón." Teoría de autómatas y lenguajes formales". McGraw-Hill (2007). Capítulos 3 y 7

• John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman. "Introducción a la teoría de autómatas, lenguajes y computación" (3ª edición). Ed, Pearson Addison Wesley.
Sects. 2.1-2.2; Sects. 2.3-2.8; HMU, Chap. 4;HMU, Sects. 3-1-3.7

• Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga. "Teoría de lenguajes, gramáticas y autómatas". Publicaciones R.A.E.C. 1997
Capítulos 4,5,y 8

JOURNALS

1)
Título: A categorical framework for finite state machines
Autor: Hines, P.
Fuente: Mathematical Structures in Computer Science June 2003, vol.13, no.3, pp. 451-80. ISSN: 0960-1295, CODEN: MCSCEA SICI: 0960-1295(200306)13:3L.451:CFFS;1-X Publisher: Cambridge University Press Country of Publication: UK

2)
Título: Products of finite state machines with full coverage
Autores: Cohen, D.M.; Fredman, M.L.
Fuente: Theoretical Computer Science 22 Jan. 1996, vol.154, no.1, pp. 57-65. ISSN: 0304-3975, CODEN: TCSCDI SICI: 0304-3975(19960122)154:1L.57:PFSM;1-P Publisher: Lund Sweden: Elsevier Country of Publication: Netherlands
3)
Título: Minimization of finite state machines using spreadsheet
Autor: Manzoul, M.A.
Fuente: Journal of Computer Information Systems Fall 2003, vol.44, no.1, pp. 235-8. ISSN: 0887-4417, CODEN: JCISE9 SICI: 0887-4417(200323)44:1L.235:MFSM;1-U Publisher: Int. Assoc. Comput. Inf. Syst Country of Publication: USA