,AlgoritmoparareducirlacomplejidadcomputacionalenlaconversióndeAFNDs AAFDs

Vista previa del material en texto

Scientia et Technica Año XVII, No 47, Abril de 2011. Universidad Tecnológica de Pereira. ISSN 0122-1701 147 
 
Fecha de Recepción: 25 de Enero de 2011 
Fecha de Aceptación: 24 de Abril de 2011 
ALGORITMO PARA REDUCIR LA COMPLEJIDAD COMPUTACIONAL EN LA 
CONVERSIÓN DE AFNDs. A AFDs. 
 
Algorithm to reduce the computational Complexity Converting an NFA to a DFA 
 
RESUMEN 
 
Al convertir un Autómata Finito No Determinístico (AFND) a un 
Autómata Finito Determinístico (AFD) los algoritmos descritos en la 
mayoría de la documentación presentan una complejidad computacional 
del tipo exponencial (O(2
n
)), lo cual no es deseable. Esto se debe a las 
múltiples combinaciones que se dan al hallar los posibles estados 
equivalentes entre autómatas. El presente trabajo propone un algoritmo 
que reduce dicha complejidad. 
 
PALABRAS CLAVES: AFD, AFND, Autómata, Complejidad 
Computacional, Estados. 
 
 
ABSTRACT 
 
When converting a non deterministic automata to a deterministic 
automata the algorithms described in most papers have an exponential 
computational complexity (O(2
n
)), which is no desired. This is due to the 
multiple combinations that are possible to find equivalent states between 
automatas. This paper proposes an algorithm that reduces this 
complexity. 
 
KEYWORDS: Automata, DFA, NFA, Computational Complexity, 
States. 
 
 
 JORGE IVAN RIOS P 
Ingeniero Industrial, 
M. Sc. Ingeniería de Sistemas, 
M. Sc Ingeniería del Conocimiento. 
Profesor Asociado. 
Programa de Ingeniería de Sistemas 
y Computación. 
Universidad Tecnológica de Pereira 
jirios@utp.edu.co 
 
HUGO HUMBERTO MORALES 
PEÑA 
Ingeniero de Sistemas. 
Profesor Auxiliar 
Programa de Ingeniería de Sistemas 
y Computación. 
Universidad Tecnológica de Pereira 
huhumor@utp.edu.co 
 
AUGUSTO ANGEL AGUDELO 
ZAPATA 
Ingeniero Electricista, Esp. 
Profesor Auxiliar 
Programa de Ingeniería de Sistemas 
y Computación. 
Universidad Tecnológica de Pereira 
a3udeloz@utp.edu.co 
 
 
1. INTRODUCCIÓN 
 
Un problema que se presenta, cuando se realizan 
transformaciones de Autómatas Finitos No Deterministas 
(AFNDs.), a Autómatas Finitos Deterministas (AFDs.), 
concretamente en su equivalencia computacional, es que 
en dicha transformación, se presenta una alta complejidad 
de tipo computacional: O(2
n
), debido a que el algoritmo 
que se propone en toda la bibliografía revisada y 
referenciada [1], [2], [3], [4], [5], [6], [7], [8] y [9], tiene 
en cuenta todas las posibles combinaciones de los estados 
del AFND, al realizar dicha transformación. 
 
Cuando se trata de pequeños AFNDs, es decir cuando el 
número de estados es pequeño (no mayor que de 4), la 
complejidad computacional de la transformación no suele 
ser impactante y se puede recurrir al algoritmo propuesto 
en la antes mencionada bibliografía. 
 
 
Lo anterior se debe, a que el algoritmos que establecen la 
equivalencia computacional entre AFNDs. y AFDs., 
basan su fundamento, en que un conjunto de estados en 
un AFND es equivalente a uno en el AFD: 
 
 , donde , y (1) 
 
En este artículo, proponemos un algoritmo, que reduce la 
complejidad en el caso promedio, en la conversión de un 
AFND a AFD. 
 
2. ALGORITMO PARA DETERMINAR LA 
EQUIVALENCIA COMPUTACIONAL ENTRE 
AFNDs. Y AFDs. 
 
2.1 Definiciones Básicas 
 
Definición: Sea un AFD, M = ( , Q, s, F, ) donde es 
el alfabeto, Q el conjunto de estados, s=q0 el estado 
inicial, F el conjunto de estados de aceptación, y es la 
función de transición : Q  → Q, y dicha función 
mailto:jirios@utp.edu.co
mailto:huhumor@utp.edu.co
mailto:a3udeloz@utp.edu.co
 Scientia et Technica Año XIII, No x, Mes de 200x. Universidad Tecnológica de Pereira. 
 
 
148 
extendida, ’ : Q  → Q, la cual queda definida 
recursivamente así: 
 
 
 
 
 
 
 
 
 
 
 (2) 
 
Por lo tanto un lenguaje aceptado por un AFD cualquiera, 
está definido, por: 
 
L(M) = { ω | ω ˄ ´(q0, ω) F} (3) 
 
De forma análoga a lo anterior, se tiene para los AFNDs., 
la siguiente definición: 
 
Definición: Sea un AFND, definido como M’ = ( , Q, s, 
F, ) donde es la relación de transición : Q  → Q, 
y dicha relación extendida, : Q  → Q, la cual 
queda definida recursivamente así: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 (4) 
 
Por lo tanto, y de manera similar que en el AFD, el 
lenguaje de aceptación, de un AFND, es: 
 
L(M’) = { ω | ω ˄ ’ (q0, ω)  F ≠ } (5) 
 
De lo anterior, es fácil determinar que si los dos 
lenguajes (4) (7) son iguales, los dos autómatas son 
equivalentes: AFD  AFND. 
 
2.2 Equivalencia Computacional entre AFDs. y 
AFNDs. 
 
La equivalencia y por lo tanto, el algoritmo para 
determinarlo, entre dos autómatas uno AFND y otro 
AFD, pasa por la demostración del anterior teorema. 
 
Según [5] [6] y [8], se debe definir el AFD en función del 
AFND así: M’’ = ( , Q’, s’, F’, ), dónde: 
 
 : Alfabeto 
Q’ : Colección de los subconjuntos de Q: P(Q) 
s’ : {q0} 
F’ : Colección de subconjuntos de Q, que contienen 
 estados de F, es decir F’ = {P Q’ | P  F ≠ } 
 : Función de transición
1
 Q’ → Q’, donde: 
 
 
1
 ahora es una función que operará sobre colecciones de estados 
 
 
 
 
 
 
 
  
 
  
 
 
 (6) 
 
Es fácil colegir, que el nuevo conjunto de estados (Q’), 
será la nueva colección de posibles subconjuntos de los 
estados del AFND, es decir 2
n+1
 estados. 
 
Por lo tanto, si Q = {qo, q1, …., qn}, entonces: 
 
Q’={{},{qo},{q1},…, {qn},...,{qo,q1},…{qo,qn}, 
 ...{q1,q2}, …,{ qo, q1, ..., qn}} 
2
 (7) 
 
Al realizar las transiciones del nuevo AFD equivalente, el 
orden de complejidad seria: 
 
m 2n+1 = O(2n), donde , (8) 
 
2.3 Ejemplo 1: 
 
Con el fin ilustrar cómo funciona el algoritmo, y 
determinar su complejidad, proponemos el siguiente 
ejemplo. 
 
Sea un AFND M’ = ( , Q, s, F, ) donde: 
 
 = {a,b} 
 Q = {qo, q1, q2} 
 s = q0 
 F = {q2} 
 Relación (definida en la Tabla 1) 
 
 
Q 
 
q0 {q1}  
q
1
 {q
1
} { q
1, q2} 
q
2
  { q2} 
Tabla 1. Relación de transiciones del AFND 
 
La representación gráfica del AFND (Figura 1) es: 
 
 
Figura 1. Diagrama de transición del AFND propuesto 
 
 
2
 En el resto del artículo de forma indiferente se utilizará el símbolo  
o el par de llaves sin elementos {} para representar el conjunto vacío. 
 
a, b 
 a b 
 b 
 q0 q1 q2 
Scientia et Technica Año XIII, No x, Mes de 200x. Universidad Tecnológica de Pereira. 
 
149 
Aplicando (6) y (7), se obtiene el siguiente AFD M’’ = 
( , Q’, s’, F’, ), equivalente: 
 
 = {a,b} 
 s’ = {q0} 
 Q’=P(Q)={{},{qo},{q1},{q2},{qo,q1},{qo,q2}, 
{q1,q2},{qo, q1, q2}} 
 F’ = {{q2},{qo,q2}, {q1,q2},{qo, q1, q2}} 
 Función (definida en la Tabla 2) 
 
 
Q’ 
 
{} {} {} 
{q0} {q1} {} 
{q
1
} {q1} {q1,q2} 
{q
2
} {} {q2} 
{qo,q1} {q1} {q1,q2} 
{qo,q2} {q1} {q2} 
{q1,q2} {q1} {q1,q2} 
{qo, q1, q2} {q1} {q1,q2} 
Tabla 2. Función de transiciones del AFD equivalente 
 
La representación gráfica del AFD equivalente (Figura 2) 
es: 
 
 
Figura 2. Diagrama de transición del AFD equivalente 
 
Eliminandolos estados inalcanzables
3
 {q2}, {qo,q1} , 
{qo,q2} y {qo,q1, q2} (en la figura 2 aparecen con círculos 
punteados), y renombrando los estados del mismo, 
obtenemos el siguiente AFD M = ( , P, s, F, ), donde: 
 
 = {a,b} 
 
3
 Un estado se define como inalcanzable, cuando a partir del estado 
inicial (q0), de manera directa o a través de otros estados accesibles 
desde q0, dicho estado no es accesible, para ningún símbolo del 
alfabeto. 
 P = {p0, p1, p2, p3}, donde P  Q’ y p0 = {q0}, 
 p1 = {q1}, p2 = {q1, q2} y p3 = {} 
 s = p0 
 F = {p2} 
 Función : P  → P, (definida en la tabla 3) 
 
 
P 
 
p0 p1 p3 
p
1
 p
1
 p
2
 
p
2
 p
1
 p
2
 
p
3
 p
3
 p
3
 
Tabla 3. Función de transiciones del AFD depurado 
 
La representación gráfica del AFD depurado (Figura 3) 
es: 
 
 
Figura 3. Diagrama de transición del AFD depurado 
 
2.4 Propuesta de un nuevo Algoritmo para reducir la 
complejidad 
 
Como se puede observar, el nuevo AFD (con diagrama 
de transición Figura 2), cuando se realiza la ejecución de 
(6) y (7), como parte del mismo del mismo algoritmo, 
aparecen ocho estados (2
|Q|
 = 2
3
), de los cuales, cuatro 
son inalcanzables, desde el estado inicial. Esto es parte 
inherente de la transformación, donde se tiene en cuenta 
todos los posibles subconjuntos del conjunto de estados 
del AFND. La magnitud, de este nuevo conjunto, es de 
orden 2
n
. 
 
La generación de la función , para el AFD equivalente, 
cuando el número de estados es alto en el AFND, la 
complejidad computacional de esta generación se vuelve 
del orden exponencial. Por ejemplo un AFND con 
cuarenta estados, generaría, en primer lugar, un conjunto 
de 2
40
 (1’099.511’627.776) subconjuntos de estados, que 
multiplicados por el número de símbolos del alfabeto, 
nos daría el total de transiciones del nuevo AFD 
equivalente. 
 
 p
0
 
 p
1
 p
2
 
a 
a a 
b 
b 
 
b 
a, b 
 p
3
 
 
a 
 a b 
 b 
 {q0} 
{q
1
} 
{q1,q2} 
a 
{qo,q1, q2} 
 
a b 
{q
0
,q
1
} 
b 
a 
{q
0
,q
2
} 
 {} 
a, b 
 
 
 b 
 
 
a 
 b 
 {q
2
} 
 
 
 
 b 
a 
 Scientia et Technica Año XIII, No x, Mes de 200x. Universidad Tecnológica de Pereira. 
 
 
150 
Obsérvese también, que en la generación de los nuevos 
estados del AFD, aparecen estados inalcanzables, lo cual 
agrega un cálculo computacional innecesario, tal como se 
puede observar en el diagrama de transición del AFD del 
ejemplo propuesto (Figura 2). 
 
Para resolver la anterior problemática, partimos del 
concepto de estado alcanzable, es decir a partir del estado 
inicial s = {q0}, en la aplicación del algoritmo solo 
tendremos en cuenta aquellos estados que se alcancen 
con cada uno de los símbolos del alfabeto. 
 
Algoritmo para transformar AFND en AFD: 
1. Inicializar 
2. Para todo 
3. Para todo 
4. Si  
5.  
6. Si  
7. 
8. 
9. 
 
Aplicando nuestro algoritmo al ejemplo anteriormente 
propuesto, se obtiene lo siguiente: 
 
 
 
 
 
 
 
Tabla 4. Paso a paso construcción función 
 
 
 
 
 
 
 
 
 
 
 
Tabla 5. Paso a paso construcción función 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 6. Paso a paso construcción función 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 7. Paso a paso construcción función 
 
 
 
Renombrando los estados como, p0 = {q0}, p1 = {q1}, 
p2 = {q1, q2} y p3 = {}, el nuevo AFD M = ( , P, s, F, ), 
donde: 
 
 = {a,b} 
 P = {p0, p1, p2, p3} 
 s = p0 
 F = {p2} 
 La función : P  → P, representada por la 
siguiente tabla: 
 
 
P 
 
p0 p1 p3 
p
1
 p
1
 p
2
 
p
2
 p
1
 p
2
 
p
3
 p
3
 p
3
 
Tabla 8. Función del ADF equivalente 
 
La tabla anterior (No 8) nos muestra que llegamos al 
mismo AFD que obtuvimos cuando aplicamos el 
algoritmo tradicional. En nuestro algoritmo no se tienen 
en cuenta todos los subconjuntos de estados (2
|Q|
), si no 
únicamente los que son accesibles desde el nuevo estado 
inicial {q0}, lo cual descarta los no accesibles y 
obviamente sus transiciones. 
 
2.5 Ejemplo 2: 
 
Con este ejemplo se deja en evidencia que no todas las 
veces se economiza trabajo con nuestro algoritmo de 
transformación de AFND a AFD versus el algoritmo 
tradicional. 
 
Sea el AFND M’ = ( , Q, s, F, ) donde: 
 
 = {a,b} 
 Q = {qo, q1, q2} 
 s = q0 
Scientia et Technica Año XIII, No x, Mes de 200x. Universidad Tecnológica de Pereira. 
 
151 
 F = {q2} 
 Relación (definida en la Tabla 9) 
 
 
 
 
 
 
 
Tabla 9. Relación de transiciones del AFND 
 
Aplicando nuestro algoritmo al AFND anterior, tenemos: 
 
 , 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 10. Paso a paso construcción función 
 
 , 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 11. Paso a paso construcción función 
 
 , 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 12. Paso a paso construcción función 
 
 , 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 13. Paso a paso construcción función 
 
 , 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 14. Paso a paso construcción función 
 
 , 
 
 
 Scientia et Technica Año XIII, No x, Mes de 200x. Universidad Tecnológica de Pereira. 
 
 
152Tabla 15. Paso a paso construcción función 
 
Ya en estos momentos contiene todos los posibles 
subconjuntos de estados de , lo que indica que todos los 
subconjuntos de estados harán parte del AFD equivalente 
al AFND. 
 
La función completa se presenta a continuación (Tabla 
16): 
 
 
 
 
 
 
 
 
 
 
 
 
Tabla 16. Función completa para el AFD equivalente 
 
Con el ejemplo anterior se evidencia que nuestro 
algoritmo en el peor de los casos genera la misma 
cantidad exponencial de estados que el algoritmo 
tradicional, donde podemos garantizar que todos estos 
son alcanzables desde el estado inicial. 
 
3. CONCLUSIONES Y RECOMENDACIONES 
 
En el algoritmo tradicional que consiste de la ecuaciones 
(6) y (7), las complejidades en el mejor y en el peor de 
los casos son de orden exponencial (Θ(2
n
)). El algoritmo 
propuesto presenta una mejora sustancial mejorando el 
mejor de los casos, obteniéndose una complejidad de 
orden lineal (O(n)) y el caso promedio se aproxima a una 
cuadrática (O(n
2
)). 
 
En un próximo artículo se determinará analíticamente la 
complejidad del caso promedio. 
 
4. BIBLIOGRAFÍA 
 
[1] Ding-Zhu Du, Ker-I Ko, Problem Solving in 
Automata, Languages, and Complexity, John Wiley 
& Sons, INC., Capítulo 2, páginas 23-53, 2001, 
ISBN 0-471-43960-6 
[2] Rodrigo De Castro Korgi, Teoría de la 
Computación, Lenguajes Autómatas y Gramáticas, 
Universidad Nacional de Colombia, Facultad de 
Ciencias, UNIBIBLOS, Bogotá D.C, Capítulo 2, 
páginas 25-42, 2004. 
[3] Dean Kelley, Teoría de Autómatas y Lenguajes 
Formales, Editorial Prentice-Hall, ISBN 0-13-
497777-7, España, Capítulo 2, páginas 53-69, 1995. 
[4] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. 
Ullman, Introduction to Automata Theory, 
Languages, and Computation, Second Edition, 
Addison-Wesley, ISBN 0-201-44124-1, United 
States of America, Capítulo 2, páginas 45-63, 2001. 
[5] Pedro García, Tomás Pérez, José Ruiz, Encarna 
Segarra, José M. Sempere, y Manuel Vásquez de 
Parga, Teoría de Autómatas y Lenguajes Formales, 
Alfaomega, ISBN 970-15-0661-8, México, Capítulo 
2, páginas 32-44, 2001. 
[6] Rafael Cases Muñoz y Lluis Márquez Villodre, 
Lenguajes Gramáticas y Autómatas, Curso Básico, 
Alfaomega, ISBN 970-15-0775-4, México, Capítulo 
4, páginas 74-88, 2002. 
[7] Pedro Isasi, Paloma Martínez y Daniel Borrajo, 
Lenguajes Gramáticas y Autómatas, Un enfoque 
Práctico, Addison-Wesley, ISBN 0-201-65323-0, 
España, Capítulo 3, páginas 63-81, 1997. 
[8] Raul Gómez Marín y Andrés Sicard, Informática 
Teórica. Elementos Propedéuticos, Fondo Editorial 
Universidad EAFIT, Sección 4.4, páginas 145-150, 
2002. 
[9] Juraj Hromkovic, Theoretical Computer Science. 
Introduction to Automata, Computability, 
Complexity, Algorithmics, Randomization, 
Communication, and Cryptography, Spinger Verlag, 
Berlin, Capítulo 3, páginas 55-87, 2004.