NFA-minimering

Inom automatteorin (en gren av teoretisk datavetenskap ) är NFA-minimering uppgiften att omvandla en given icke-deterministisk finit automat (NFA) till en ekvivalent NFA som har ett minsta antal tillstånd, övergångar eller båda. Medan det finns effektiva algoritmer för DFA-minimering är NFA-minimering PSPACE-komplett . Inga effektiva (polynomiell tid) algoritmer är kända, och under standardantagandet P ≠ PSPACE existerar ingen. Den mest effektiva kända algoritmen är Kameda‒Weiner-algoritmen.

Icke-unikhet hos minimal NFA

Till skillnad från deterministiska finita automater kanske minimala NFA inte är unika. Det kan finnas flera NFA:er av samma storlek som accepterar samma vanliga språk , men för vilka det inte finns någon motsvarande NFA eller DFA med färre delstater.

externa länkar

• En modifierad C#-implementering av Kameda-Weiner (1970) [1]