Minimalizacja NFA

W teorii automatów (gałąź informatyki teoretycznej ) minimalizacja NFA polega na przekształceniu danego niedeterministycznego automatu skończonego (NFA) w równoważny NFA, który ma minimalną liczbę stanów, przejść lub jedno i drugie. Chociaż istnieją wydajne algorytmy minimalizacji DFA , minimalizacja NFA jest PSPACE-complete . Nie są znane żadne wydajne (czas wielomianowy) algorytmy i przy standardowym założeniu P ≠ PSPACE , żaden nie istnieje. Najbardziej wydajnym znanym algorytmem jest algorytm Kamedy-Weinera.

Nieunikalność minimalnego NFA

W przeciwieństwie do deterministycznych automatów skończonych , minimalne NFA mogą nie być unikalne. Może istnieć wiele NFA tej samej wielkości, które akceptują ten sam język regularny , ale dla których nie ma odpowiednika NFA lub DFA z mniejszą liczbą stanów.

Linki zewnętrzne

• Zmodyfikowana implementacja C# autorstwa Kameda-Weiner (1970) [1]