Existe-t-il un moyen de tester si deux NFA acceptent la même langue?

10

Ou au moins générer un ensemble de chaînes qu'un NFA accepte, donc je peux le nourrir dans l'autre NFA. Si je fais une recherche à travers tous les chemins de la NFA, cela fonctionnera-t-il? Bien que cela prenne beaucoup de temps.

algorithms regular-languages finite-automata Duncan
la source
Non (pas à notre connaissance, du moins). L'égalité NFA est complète sur PSPACE. Voir cette discussion .
Shaull
@Shaull: L'OP n'a pas été efficace .
frafl
@frafl: Vous avez raison. J'ai supposé par "cela prendra longtemps" que le PO souhaite une solution efficace. Pourtant, mon commentaire mentionne que c'est dans PSPACE, donc c'est décidable.
Shaull

Réponses:

10

Le problème de décision est PSPACE-complet comme Shaull l'a noté.

Cependant, il s'avère que dans la pratique, il est souvent possible de décider de l'équivalence NFA assez rapidement. Mayr et Clemente (sur la base de preuves expérimentales) affirment que la complexité moyenne des cas évolue de façon quadratique . Leurs techniques reposent sur l'élagage du système de transition étiqueté sous-jacent via des approximations locales des inclusions de traces.

Tout comme SAT est NP-complet dans une analyse du pire des cas, mais s'avère souvent étonnamment exploitable pour les instances du monde réel, il semble donc probable que l'équivalence NFA puisse être décidée efficacement pour de nombreuses instances du monde réel.

András Salamon
la source