Dlaczego minimalizacja NFA jest trudnym problemem, gdy minimalizacja DFA nie jest?

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.

Dla DFA istnieje ładna struktura algebraiczna, która określa, które stany mogą być równoważne, równoważność Myhill-Nerode na łańcuchach jest związana z minimalizacją DFA.

W przypadku NFA sytuacja jest skomplikowana, ponieważ ogólnie nie ma unikalnego minimalnego NFA.

Oto przykład języka skończonego . Oba automaty są minimalne stanowe. Przykład pochodzi z pracy Uwaga na temat minimalnych niedeterministycznych automatów Arnolda, Dicky'ego i Nivata.$\{ ab, ac, bc, ba, ca, cb\}$

Ta odpowiedź próbuje wyrazić fakt, że dwa problemy są „technicznie” różne. Zobacz odpowiedź vzn, aby dowiedzieć się, jak różnią się problemy w złożoności obliczeniowej.

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łowo$pq$ 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 stan$Q$ 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 śledzenia $n$ stwierdza do $2^n$ podzbiory stanów w najgorszym przypadku utrudniają zminimalizowanie NFA.

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łania$O(ns \log n)$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