Algoritmo de Optimización del Autómata Finito Determinista

El objetivo es obtener el autómata finito determinista mínimo equivalente de un AFD, mediante la eliminación del número de estados posibles. Para esto es necesario buscar los estados equivalentes existentes.

Figura 1.16

En la Figura anterior B y C son equivalentes, porque al unirlos no cambia su configuración en la aceptación o rechazo de palabras, o sea, los dos estados tienen la misma condición de aceptación (son finales) y su alfabeto de entrada es el mismo (d).

Cuando dos estados son equivalentes, se elimina uno para evitar redundancias. El problema de esta acción radica en qué hacer con las flechas que conectan el estado eliminado con el resto. Esto se soluciona con los siguientes criterios (4):

• Las flechas que salen del estado eliminado son eliminadas. 
• Las flechas que llegan al estado eliminado son redirigidas hacia su estado equivalente.

Algoritmo para la minimización del AFD mediante una Tabla de Estados Equivalentes. 

Construir Tabla: Las filas y columnas están etiquetadas con estados. Representando una pareja de estados del autómata. Ejemplo: Del AFD (Figura 1.16) su Tabla de estados equivalentes es:

A		simétrico	simétrico
B			simétrico
C
	A	B	C

Esta tabla se construye de forma optimizada, o sea, triangular porque se buscan relaciones de equivalencia:

B
C
	A	B

Marcar estados distinguibles en la tabla: Se realiza un recorrido de izquierda a derecha y cada columna de arriba a abajo. En este caso los pares distinguibles son (A, B) y (A, C). Siendo el par (B, C) posibles equivalentes.

B	X
C	X
	A	B

Analizar posibles estados equivalentes: Para analizar si los estados son equivalentes, se utilizan sus alfabetos de entrada. En este caso sería (d).

Si se analiza el par (B, C), a la vez se analiza (C, B) porque se cumple la propiedad simétrica de una relación binaria de equivalencia.

δ(B, d) = C , δ(C, d) = C  se forma el par (C, C). Al analizar este par
equivalente se halla en la diagonal. Si el par formado en la tabla se 
encuentra marcado entonces no es equivalente y se marca, de lo contrario,
 es equivalente.

B	X
C	X	(B, C)
	A	B

Al terminar el recorrido, los estados equivalentes se unen, teniendo en cuenta los criterios mencionados.

B	(B, C)
C	X
	A	B

Si se analiza la casilla (B, C) y no son equivalentes, la casilla (A, B) se marca como no equivalente porque contiene a este par

B	√
C	X	√
	A	B

Ejemplo: AFD equivalente de la expresión regular c+|d|aac*|ba

Se construye la tabla y se marcan los distinguibles

q2	X
q3	X
q4		X	X
q5		X	X
q6	X			X	X
q7	X			X	X
	q1	q2	q3	q4	q5	q6

 

Al analizar la casilla (q1, q4): los alfabetos de entrada son {a, b, c, d}, como para cada cadena de entrada x, δ(q1, x) ≡ δ (q4, x), y se elabora latabla de transición de equivalencia

	a	d	c	d
q1	q4	q5	q2	q3
q4	q6

Tabla de transición de equivalencia: Forma de representar δ(q, x) ≡ δ (p, x) siendo (x) una cadena de entrada. Las intersecciones de fila y columna muestran el próximo estado con la cadena de entrada específica. Si contiene la tabla una casilla vacía, los estados q y p no son equivalentes. Pero cuando todas las casillas se marcan, o sea, están ocupadas, los pares que se forman son responden a la unión del superior con el inferior. Ejemplo: (q4,q6). Como los estados q1 y q4 no son equivalentes, se marca la casilla

q2	X
q3	X
q4	√	X	X
q5		X	X
q6	X			X	X
q7	X			X	X
	q1	q2	q3	q4	q5	q6

Al analizar la casilla (q1, q5): los alfabetos de entrada son {a, b, c, d}, como para cada cadena de entrada x,δ(q1, x) ≡ δ (q5, x), elaborándose lasiguiente tabla de transición de equivalencia.

	a	d	c	d
q1	q4	q5	q2	q3
q5	q7

Como los estados q1 y q5 no son equivalentes, se marca la casilla

q2	X
q3	X
q4	√	X	X
q5	√	X	X
q6	X			X	X
q7	X			X	X
	q1	q2	q3	q4	q5	q6

Al analizar la casilla (q2, q3): elalfabeto de entrada es {c}, como para cada cadena de entrada x,δ(q2, x) ≡ δ (q3, x), se elabora la tabla de transición de equivalencia

	c
q2	q2
q3

Los estados q2 y q3 no son equivalentes, se marca la casilla

q2	X
q3	X	√
q4	√	X	X
q5	√	X	X
q6	X			X	X
q7	X			X	X
	q1	q2	q3	q4	q5	q6

 
Al analizar la casilla (q2, q6): el alfabeto de entrada es{c}, como para cada cadena de entrada x,δ(q2, x) ≡ δ (q6, x), y se elabora la tabla de transición de equivalencia

	c
q2	q2
q6	q6

El par formado (q2, q6), no se encuentra marcada la casilla. Por ende, los estados q2 y q6 son equivalentes, y se marca la casilla

q2	X
q3	X	√
q4	√	X	X
q5	√	X	X
q6	X	(q2, q6)		X	X
q7	X			X	X
	q1	q2	q3	q4	q5	q6

Al analizar la casilla (q2, q7): el alfabeto de entrada es{c}, como para cada cadena de entrada x,δ(q2, x) ≡ δ (q7, x) y se elabora la tabla de transición de equivalencia

	c
q2	q2
q7

Los estados q2 y q7 no son equivalentes, por lo que se marca la casilla

q2	X
q3	X	√
q4	√	X	X
q5	√	X	X
q6	X	(q2, q6)		X	X
q7	X	√		X	X
	q1	q2	q3	q4	q5	q6

Al analizar la casilla (q3, q6): el alfabeto de entrada es {c}, como para cada cadena de entrada x,δ(q3, x) ≡ δ (q6, x)y se elabora la tabla de transición de equivalencia

	c
q3
q6	q6

Los estados q3 y q6 no son equivalentes, de ahí que se marque la casilla

q2	X
q3	X	√
q4	√	X	X
q5	√	X	X
q6	X	(q2, q6)	√	X	X
q7	X	√		X	X
	q1	q2	q3	q4	q5	q6

 

Al analizar la casilla (q3, q7): no contienen alfabetos de entrada. En este caso los dos estados tienen la condición de aceptación. Se marcan como equivalentes

q2	X
q3	X	√
q4	√	X	X
q5	√	X	X
q6	X	(q2, q6)	√	X	X
q7	X	√	(q3, q7)	X	X
	q1	q2	q3	q4	q5	q6

Al analizar la casilla (q4, q5): el alfabeto de entrada es {a}, como para cada cadena de entrada x,δ(q4, x) ≡ δ (q5, x) y se elabora la tabla de transición de equivalencia

	a
q4	q6
q5	q7

Al analizar los siguientes pares: Si se revisa en la tabla el par (q6, q7)no se encuentra la casilla marcada, por tanto q4 y q5 son equivalentes

q2	X
q3	X	√
q4	√	X	X
q5	√	X	X	(q6, q7)
q6	X	(q2, q6)	√	X	X
q7	X	√	(q3, q7)	X	X
	q1	q2	q3	q4	q5	q6

Al analizar la casilla (q6, q7): el alfabeto de entrada es {c}, como para cada cadena de entrada x,δ(q6, x) ≡ δ (q7, x). y se elabora la tabla de transición de equivalencia

	c
q6	q6
q7

Los estados q6 y q7 no son equivalentes, si se observa en la tabla, en la casilla (q4, q5) se encuentra el par (q6, q7)por ende q4 y q5 no son equivalentesyse marca la casilla

q2	X
q3	X	√
q4	√	X	X
q5	√	X	X	√
q6	X	(q2, q6)	√	X	X
q7	X	√	(q3, q7)	X	X	√
	q1	q2	q3	q4	q5	q6

Los estados equivalentes son: q2 ≡ q6, q3 ≡ q7, siendo el autómata finito determinista optimizado

Recomendacion: Leer:

Expresiones regulares a partir del autómata finito equivalente: Parte I 

Expresiones regulares a partir del autómata finito equivalente: Parte II 

Algoritmo de conversión de expresión regular a aut...


 Algoritmo de conversión de Autómata finito no determinista a un Autómata finito determinista

Referencias Bibliográficas 

1. Pérez Martínez, Abel. ERAFPLN. 2009.
2. PÉREZ, NALLY CAMPO. INTRODUCCIÓN A LA TEORÍA DE CONJUNTOS. [En
línea] http://www.e-socrates.org/mod/resource/view.php?id=4398.
3. REAL ACADEMIA ESPAÑOLA. [En línea] http://buscon.rae.es/draeI/.
4. Brena, Ramón. AUTOMATAS Y LENGUAJES. Monterrey : s.n., 2003.
5. Hopcroft, John E. Introducion to automata theory, languages, and computation.
s.l. : Addison-Wesley, 2001.
6. Lawson, M. V. Finite automata.
http://www.ma.hw.ac.uk/~markl/preprints/Lawson.pdf. [En línea] 
7. RegExlib. [En línea] http://regexlib.com/default.aspx.
8. Javascript Regular Expression Validator. [En línea]
http://tools.netshiftmedia.com/regexlibrary/.
9. RegexPal. [En línea] http://regexpal.com/.
10. metriplica.com, Grupo. ¡Prueba tus Expresiones Regulares!
http://www.metriplica.com/4_4_herramientas.asp. 2008.
11. Regular Expression Tool. [En línea]
http://erik.eae.net/playground/regexp/regexp.html.
12. Regexp Editor. [En línea] http://myregexp.com/.
13. Rad Software Regular Expression Designer 1.4.7528.27091. [En línea]
http://www.radsoftware.com.au/?from=RegexDesigner.
14. Visual REGEXP 3,0. [En línea] http://www.softpedia.com/get/Programming/OtherProgramming-Files/Visual-REGEXP.shtml.
15. Regulazy v1.0.3.0 (Beta). [En línea] http://tools.osherove.com/Default.aspx.
16. Regular Expression Workbench. [En línea] EricGu@Microsoft.Com.
17. Sells, Chris and Weinhardt, Michael. RegexDesigner v1.0.2727. [En línea]
http://www.sellsbrothers.com/tools/.
18. Visual Automata Simulator. [En línea] http://www.cs.usfca.edu/~jbovet/.
19. Acosta, Francisco Ríos. SP-PS1. [En línea] http://www.friosa.com.mx.
20. RegexBuddy3. [En línea] http://www.regexbuddy.com/.
21. The Software Process Dashboard Initiative. [En línea]
http://www.processdash.com/.
22. METODOLOGÍA DE MUESTREO. [En línea]
http://www.hsa.es/id/investigacion/uai/uai_docs/muestreo/muestreo.htm.
23. Modelos Abstractos de Cómputo I. [En línea]
http://www.sc.ehu.es/jiwnagom/MAC1/MAC-archivos/Tema2-parte3.pdf.