Algoritmo para reducir la complejidad computacional en la conversión de AFNDs. A AFDs. - Morales Peña, Hugo Humberto; Agudelo, Angel Augusto; Rios Patiño, Jorge Iván (Scientia et Technica, 2011)
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(2n)), 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.