O al menos generar un conjunto de cadenas que una NFA acepta, para que pueda alimentarlo a la otra NFA. Si hago una búsqueda en cada ruta de la NFA, ¿funcionará? Aunque eso llevará mucho tiempo.
10
O al menos generar un conjunto de cadenas que una NFA acepta, para que pueda alimentarlo a la otra NFA. Si hago una búsqueda en cada ruta de la NFA, ¿funcionará? Aunque eso llevará mucho tiempo.
Respuestas:
El problema de decisión es PSPACE-complete como lo señaló Shaull.
Sin embargo, resulta que en la práctica a menudo es posible decidir la equivalencia de NFA razonablemente rápido. Mayr y Clemente (basados en evidencia experimental) afirman que la complejidad del caso promedio se escala cuadráticamente . Sus técnicas se basan en la poda del sistema de transición etiquetado subyacente a través de aproximaciones locales de inclusiones de trazas.
Al igual que SAT es NP-completo en un análisis del peor de los casos, pero a menudo resulta sorprendentemente manejable para instancias del mundo real, por lo tanto, parece probable que la equivalencia de NFA se pueda decidir eficientemente para muchas instancias del mundo real.
fuente