Minimización de NFA sin determinación

Question

Es bien conocido cómo se obtiene de un NFA para un lenguaje normal a un mínimo de DFA. Sin embargo, el DFA podría tener un número exponencialmente mayor de estados.

Lo que necesito es una forma de reducir un NFA, dando de nuevo un NFA pero con un menor número de estados. T.i. No necesito que el resultado sea determinista, pero me gustaría que sea lo más pequeño posible mientras se preserva el lenguaje reconocido (quizás no sea absolutamente óptimo, pero cuanto más pequeño, mejor).

¿Cuáles son los mejores algoritmos para este problema? ¿O tal vez no sea "lo mejor", pero al menos "el más fácil de implementar con una eficiencia no abismal"? ¿O el problema tiene un nombre conocido para que yo pueda encontrar buenas fuentes de información?

Answer 1

Creo que el problema también se conoce como minimización NFA también. Es NP-hard en general, creo.

Un enfoque fructífero puede ser Minimización de bisimulación [Paige, Tarjan 1987], y derivados posteriores.

This presentation tiene algunas notas sobre la manejabilidad del problema, así como referencias a algunos enfoques con sus méritos relativos deletreados.

Answer 2

Hay una implementación del algoritmo de Kameda-Weiner para la minimización de la NFA aquí: https://github.com/coder0xff/parlex/blob/master/IDE/Nfa.cs