Czy istnieje sposób sprawdzenia, czy dwa NFA akceptują ten sam język?

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.

algorithms regular-languages finite-automata

— Duncan
źródło

Nie (przynajmniej według naszej wiedzy). Równość NFA jest kompletna z PSPACE. Zobacz tę dyskusję .

— Shaull

@Shaull: OP nie był tak efektywny .

— frafl

@frafl: Masz rację. Zakładam, że „zajmie to dużo czasu”, że PO chce skutecznego rozwiązania. Mimo to mój komentarz wspomina, że jest w PSPACE, więc jest rozstrzygalny.

— Shaull

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.

Richard Mayr i Lorenzo Clemente, Zaawansowana minimalizacja automatów , POPL 2013, doi: 10.1145 / 2429069.2429079 ( preprint )

— András Salamon
źródło