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?
automata
finite-automata
proof-techniques
nondeterminism
IAmOnStackExchange
źródło
źródło
Odpowiedzi:
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.
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.
źródło
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.
źródło
pytanie to dotyczy raczej testowania stosowanego oprogramowania i weryfikacji poprawności w praktyce niż pytania teoretycznego.
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.
źródło