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

14

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.

Duncan
źródło

Odpowiedzi:

8

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.{zab,zado,bdo,bza,doza,dob}

dwa NFA dla tego samego języka

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.

Hendrik Jan
źródło
8
Ani najkrótsza ścieżka, ani problem minimalnego drzewa rozpinającego (zawsze) nie mają unikalnych rozwiązań, ale nadal można je skutecznie rozwiązać.
Raphael
5

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łowopq 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 śledzenia n stwierdza do 2)n podzbiory stanów w najgorszym przypadku utrudniają zminimalizowanie NFA.

András Salamon
źródło
1

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(nslogn)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

vzn
źródło
Nie wiem, jak zdefiniować trudne, ale miałem na myśli, że nie ma wydajnego algorytmu do jego rozwiązania.
Duncan
@ Duncan ok, to rzeczywiście użyłeś tego słowa w sensie technicznym. więc jest pewne wyjaśnienie dotyczące twardości technicznej. w CS „wydajny” to także termin techniczny przyjęty / zdefiniowany jako taki sam jak PTime. więc twoje pytanie jest w rzeczywistości związane z ważnym otwartym pytaniem w TCS - powszechnie podejrzewa się / formułuje, że minimalizacja NFA (wraz z wszystkimi kompletnymi problemami z PSpace) jest rzeczywiście „trudna”, tj. nie w P, ale nie została jeszcze udowodniona.
vzn