Oder generieren Sie zumindest eine Reihe von Zeichenfolgen, die eine NFA akzeptiert, damit ich sie in die andere NFA einspeisen kann. Wenn ich jeden Pfad der NFA durchsuche, funktioniert das dann? Obwohl das lange dauern wird.
10
Oder generieren Sie zumindest eine Reihe von Zeichenfolgen, die eine NFA akzeptiert, damit ich sie in die andere NFA einspeisen kann. Wenn ich jeden Pfad der NFA durchsuche, funktioniert das dann? Obwohl das lange dauern wird.
Antworten:
Das Entscheidungsproblem ist PSPACE-vollständig, wie Shaull feststellte.
Es stellt sich jedoch heraus, dass es in der Praxis häufig möglich ist, die NFA-Äquivalenz relativ schnell zu bestimmen. Mayr und Clemente (basierend auf experimentellen Beweisen) behaupten, dass die Komplexität des Durchschnittsfalls quadratisch skaliert . Ihre Techniken beruhen auf dem Beschneiden des zugrunde liegenden markierten Übergangssystems durch lokale Approximationen von Spureneinschlüssen.
So wie SAT in einer Worst-Case-Analyse NP-vollständig ist, sich jedoch für reale Instanzen oft als überraschend nachvollziehbar herausstellt, scheint es daher wahrscheinlich, dass die NFA-Äquivalenz für viele reale Instanzen effizient entschieden werden kann.
quelle