Lub przynajmniej wygeneruj zestaw ciągów, które akceptuje jeden NFA, więc mogę wprowadzić go do drugiego NFA. Czy jeśli przeszukam wszystkie ścieżki NFA, czy to zadziała? Chociaż zajmie to dużo czasu.
10
Lub przynajmniej wygeneruj zestaw ciągów, które akceptuje jeden NFA, więc mogę wprowadzić go do drugiego NFA. Czy jeśli przeszukam wszystkie ścieżki NFA, czy to zadziała? Chociaż zajmie to dużo czasu.
Odpowiedzi:
Jak zauważył Shaull, problemem decyzyjnym jest ukończenie PSPACE.
Okazuje się jednak, że w praktyce często można dość szybko zdecydować o równoważności NFA. Mayr i Clemente (na podstawie dowodów eksperymentalnych) twierdzą, że złożoność średnich przypadków skaluje się kwadratowo . Ich techniki polegają na przycinaniu leżącego u podstaw systemu znakowanego przejścia przez lokalne przybliżenia wtrąceń śladowych.
Podobnie jak SAT jest NP-kompletny w analizie najgorszego przypadku, ale często okazuje się zaskakująco możliwy do zastosowania w rzeczywistych instancjach, dlatego wydaje się prawdopodobne, że równoważność NFA można skutecznie ustalić dla wielu rzeczywistych instancji.
źródło