Wiem, że możemy zminimalizować DFA poprzez znajdowanie i łączenie równoważnych stanów, ale dlaczego nie możemy zrobić tego samego z NFA? Nie szukam dowodu ani nic takiego - chyba że dowód jest łatwiejszy do zrozumienia. Chcę tylko intuicyjnie zrozumieć, dlaczego minimalizacja NFA jest tak trudna, gdy minimalizacja DFA nie jest.
14
Zapytałeś o intuicyjne ujęcie.
W DFA dowolny prefiks wejściowy może osiągnąć tylko jeden stan. Następnie można połączyć ze sobą pary stanów, których nie można odróżnić dla żadnego przyrostka. Nie można scalić stanów, które można odróżnić za pomocą przyrostka. Prowadzi to do minimalnego automatu, który jest izomorficzny dla wszystkich innych minimalnych automatów.
W przeciwieństwie do tego, jeśli automat nie jest deterministyczny, wówczas połączenie pojedynczych stanów nierozróżnialnych przyrostkiem nie jest wystarczająco dobre. Dla danych wejściowych nie wszystkie sekwencje przejść w NFA muszą doprowadzić do stanu akceptacji: jeśli istnieje tylko jedna taka sekwencja, wystarczy, aby NFA mógł zaakceptować. Aby poprawnie zdecydować, czy można połączyć dwa stany, konieczne może być śledzenie większej ilości informacji niż w przypadku DFA. Załóżmy na przykład, że istnieje słowop q w języku z prefiksem p powoduje to pewien stan P. , ale tak, że z P. sufiks nie zawiera stanu akceptującego q . Możliwe jest, że istnieje inny stanQ to jest nie do odróżnienia P. według dowolnego przyrostka innego niż q . W takim przypadku chciałoby się połączyćP. i Q . Trzeba więc rozszerzyć pojęcie, kiedy państwa są nierozróżnialne, aby uwzględnić takie „fantomowe” różnice. Zasadniczo wymaga to śledzenia wszystkich możliwych podzbiorów stanów .
Przechodzę od śledzenian stwierdza do 2)n podzbiory stanów w najgorszym przypadku utrudniają zminimalizowanie NFA.
źródło
pytanie nie definiuje „twardego”, podczas gdy w TCS istnieje techniczne znaczenie tego słowa. w jednym sensie, ani nie jest „trudny” (minimalizujący DFA lub NFA), ponieważ istnieje wiele algorytmów dla obu. jednak pod innym kątem. Minimalizacja DFA ma czas działaniaO ( n s logn ) gdzie s jest liczbą stanów, tj. PTime. Udowodniono, że minimalizacja NFA jest kompletna. Minimalizacja NFA nie jest stosowana w PTime, chyba że P = PSpace, które powszechnie uważa się za nieprawdę.
zobacz także to pytanie TCS.se obliczające minimalną wartość NFA dla DFA
źródło