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

La conversión de un AFND-vacía o AFND en un AFD se basa en el concepto de Clausura de Kleene o Operador estrella que se describe como A*.

A es un subconjunto de A* que contiene la secuencia vacía y este último es un sistema de las secuencias que se forman con las concatenaciones de cero o más secuencia de A.


La clausura(q), siendo q un estado, es el conjunto de todos los estados que se acceden a partir de q, con un símbolo de entrada.

La transformación de un AFND a AFD se realiza a través de la tabla de transición del autómata finito no determinista, siendo cada entrada un conjunto de estado. Mientras en la tabla de transición del autómata finito determinista, cada entrada del alfabeto es un solo estado. Cada estado del AFD deviene un conjunto de estados del AFND. El estado inicial y el alfabeto del AFND es el mismo para el AFD.

Conversión de AFND-vacía a AFD

A medida que se obtienen los conjuntos del autómata, se calcula la tabla de transición. A medida que se obtienen los conjuntos del autómata, se calcula la tabla de transición.

Iteración 1: Al comenzar con q0 (estado inicial) se obtendría la clausura(q0), es decir, todos los estados alcanzados con transiciones vacía desde este estado. Los estados serían{q1, q2}, a este Conjunto lo llamaremos A.

	a	d	Aceptación
A={q0}∪{q1, q2}

Iteración 2: Se calculan todos los estados alcanzables con la letra a y d desde cada elemento del Conjunto A. Con la letra d desde q6 se llega a q3 y no se alcanza ningún estado. Con a desde q1 se llega a q6 y desde q2 se llega a q7 formando el conjunto {q6, q7} al cual se le aplica la clausura a q6 y q7 siendo los estados alcanzables con transiciones vacía el conjunto {q18, q4, q5}que forman el conjunto B. Como q5 es un estado de aceptación adquiere B la condición de estado final.

	a	d	Aceptación
A={q0}∪{q1, q2}	B={q6, q7}∪{q18, q4, q5}
B={q6, q7}∪{q18, q4, q5}			sí

Iteración 3: Se calculan todos los estados alcanzables con la letra a y d desde cada elemento del Conjunto B. Con la letra d desde q6 se llega a q3, desde q18 a q19 formando el conjunto {q3, q19}al cual se aplica la clausura y forman el conjunto {q5, q18, q4}, y la unión de ambos conjuntos da como resultado el conjunto C. Como q5 es un estado aceptación, C se convierte en estado final. Con la letra a no se alcanza ningún estado.

	a	d	Aceptación
A={q0}∪{q1, q2}	B={q6, q7}∪{q18, q4, q5}
B={q6, q7}∪{q18, q4, q5}		C={q3, q19}∪{q5, q18, q4}	sí
C={q3, q19}∪{q5, q18, q4}			sí

Iteración 4: Se calculan todos los estados alcanzables con la letra a y d desde cada elemento del Conjunto C. Con la letra a no alcanza ningún estado. Con la letra d desde q18 se llega a q19, formando el conjunto {q19} al cual se le aplica la clausura emergiendo el conjunto {q3, q5, q18, q4}. Al unir estos dos conjunto se forma de nuevo el conjunto C.

	a	d	Aceptación
A={q0}∪{q1, q2}	B={q6, q7}∪{q18, q19, q4, q5}
B={q6, q7}∪{q18, q4, q5}		C={q3, q19}∪{q5, q18, q4}	sí
C={q3, q19}∪{q5, q18, q4}		C={q19}∪{q3, q5, q18, q4}	sí

Iteración 5 y final: No existe conjunto nuevo a analizar. Obteniendo la tabla del AFD equivalente.

	a	d	Aceptación
A	B
B		C	sí
C		C	sí

Los conjuntos se transforman en estados. A es el estado inicial, B y C son estados aceptados o finales, porque como conjunto contienen a q5 y heredan sus propiedades. Siendo el autómata finito determinista:

Conversión de AFND a AFD

La expresión regular ad|ad* puede obtener un AFND equivalente:

A medida que se obtienen los conjuntos del autómata, se calcula la tabla de transición.

Iteración 1: Al comenzar con q0 (estado inicial) denominado A, se calculan todos los estados alcanzables con la letra a y d. Con la letra a desde q0 se llega a q1 y q2, formando el conjunto {q1, q2} denominado B. Con la letra d no alcanza ningún estado.

	a	d
A={q0}	B={q1, q2}
B

Iteración 2: Se calculan todos los estados alcanzables con la letra a y d del conjunto {q1, q2} Con la letra a no se alcanza ningún estado. Con la letra d desde q1 se llega a q3 y desde q2 se llega a q4, formando el conjunto C{q3, q4}.

	a	d
A={q0}	B={q1, q2}
B		C={q3, q4}
C

Iteración 3: Se calculan todos los estados alcanzables con la letra a y d desde cada elemento del Conjunto C. Con la letra a no se alcanza ningún estado. Con la letra d desde q3 se llega a q3, formando el conjunto {q3}que pertenece a C.

	a	d
A={q0}	B={q1, q2}
B		C={q3, q4}
C		C

Iteración 4: No existe conjunto nuevo a analizar.

	a	d	Aceptación
A	B
B		C	sí
C		C	sí

 

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

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.