Jak sprawdzić, czy DFA jest równoważne z NFA?

10

Uczę się, jak konwertować NFA na DFA i chcę się upewnić, że robię to dobrze. Oczywiście powrót w innym kierunku nie jest niczym. Czy ktoś zna algorytm sprawdzający, czy DFA jest równoważne z NFA?

— IAmOnStackExchange
źródło

Jedna interpretacja kandydacka: czy istnieje „moduł sprawdzania wyników” (w sensie Wassermana i Bluma ) dla problemu konwersji NFA w DFA? Innymi słowy, czy istnieje algorytm, który jest asymptotycznie szybszy niż sama konwersja, który przy rzekomej parze (wejściowej, wyjściowej) dla algorytmu konwersji-sprawdza, czy dane wyjściowe są prawidłowe?

— DW

7

To jest problematyczne pytanie. Istnieje sposób na sprawdzenie równoważności automatów, który teraz wyjaśnię, ale obawiam się, że to ci nie pomoże, jak zobaczycie na końcu.

$A$ $B$ $A\subseteq B$ $B\subseteq A$ $L(D)\subseteq L(N)$ $L(N)\subseteq L(D)$ $D$ $N$

$A\subseteq B$ $A\cap \overline{B}=\emptyset$ $\overline{B}$ $B$

$L(N)\subseteq L(D)$ $D$ $N$

$L(D)\subseteq L(N)$ $N$

Zasadniczo problem z twoim pytaniem jest znacznie głębszy: chcesz sprawdzić, czy (niezdefiniowany model obliczeniowy) poprawnie wykonałeś dobrze zdefiniowany algorytm. Więc to nie jest tak naprawdę problem informatyczny.

$L(D)\neq L(N)$ $2^{2n}$ $n$ $N$

— Shaull
źródło

Dziękujemy za przemyślaną odpowiedź. Nauczyłem się dzisiaj czegoś nowego. Wygląda na to, że moim najlepszym założeniem jest porównanie mojej pracy z JFLAP.

— IAmOnStackExchange

2

O ile twój NFA nie jest duży (np. Z więcej niż 7-8 stanami), najlepszym rozwiązaniem jest sprawdzenie się dokładnie. Zwykle po usunięciu stanów nieosiągalnych otrzymujesz mały DFA, a ręczne sprawdzenie nie jest zbyt trudne.

— Shaull,

1

Czy nie możesz określić i zminimalizować obu maszyn i sprawdzić, czy obie maszyny są izomorficzne?

— saadtaame

5

Jednym ze sposobów postępowania jest konwersja NFA do DFA, a następnie sprawdzenie równoważności dwóch DFA, dla których istnieje algorytm liniowy [1].

Poniższy artykuł dotyczy bardziej ogólnego przypadku równoważności dwóch NFA (co oczywiście dotyczy również twojego przypadku).

Filippo Bonchi, Damien Pous, Sprawdzanie równoważności NFA z bisimulacjami aż do zgodności Zasada języków programowania (POPL), styczeń 2013, Roma, Włochy. ACM, s. 457–468, 2013.

Abstrakcyjny . Wprowadzamy bisimulację aż do zgodności jako technikę dowodzenia równoważności językowej niedeterministycznych automatów skończonych. Wykorzystując tę technikę, opracowujemy optymalizację klasycznego algorytmu autorstwa Hopcroft i Karp [1]. Porównujemy nasze podejście do ostatnio wprowadzonych algorytmów antichain, analizując i łącząc dwie leżące u podstaw metody dowodu koindukcyjnego. Podajemy konkretne przykłady, w których wykładniczo poprawiamy w stosunku do antichains; wyniki eksperymentalne wykazują ponadto znaczącą poprawę.

[1] JE Hopcroft i RM Karp. Algorytm liniowy do testowania równoważności automatów skończonych. TR 114, Cornell Univ., Grudzień 1971.

Zobacz także załącznik internetowy do tego dokumentu , który zawiera skrypty potwierdzające wyniki Coq, link do implementacji i interaktywny aplet.

— J.-E. Kołek
źródło

Jednym ze sposobów postępowania jest konwersja NFA do DFA , celem plakatu jest zweryfikowanie wyniku tego algorytmu. Dwukrotne zastosowanie jest rzeczywiście jednym sposobem, ale nie jest odporne na niezrozumienie algorytmu. Prawdopodobnie dlatego zapytano o metodę sprawdzania.

— AProgrammer

2

@aprogrammer Główną częścią mojej odpowiedzi jest odwołanie do algorytmu, dla którego dostępny jest skrypt sprawdzający Coq, co jest z pewnością najbezpieczniejszą metodą sprawdzania, jaką mogę wymyślić.

— J.-E.

1

Nie jestem pewien, co zrobi ktoś, kto nie jest pewien swojego prostego algorytmu, takiego jak NFA do DFA, ze skryptem sprawdzającym Coq. Wygląda to na użycie algebry do rozwiązania problemu matematycznego trzeciej równiarki.

— AProgrammer

0

pytanie to dotyczy raczej testowania stosowanego oprogramowania i weryfikacji poprawności w praktyce niż pytania teoretycznego.

$D_1 \cap \bar{D_2}$ $D_2 \cap \bar{D_1}$ $\bar{D}$
możesz polegać na wcześniej przetestowanym oprogramowaniu, które zostało przetestowane w celu potwierdzenia wyników. np. biblioteka AT&T FSM
inny pomysł: testy losowe. wybierz losowe ciągi w swoim języku. ustalić, czy ciągi są akceptowane, czy nieakceptowane przez DFA / NFA. jeśli dwa nie są równe, z dużym prawdopodobieństwem znajdziesz ciągi, które są niezgodne.
inny pomysł: możesz napisać kod, aby przejść do niektórych gałęzi DFA i NFA na określoną głębokość i poszukać niezgodności. jest to równoważne z wyliczeniem wszystkich potencjalnych akceptowanych ciągów o danych długościach.

— vzn
źródło