Najmniejszy DFA, który akceptuje podane ciągi i odrzuca inne podane ciągi

11

Biorąc pod uwagę dwa zbiory ciągów znaków nad alfabetem , czy możemy obliczyć najmniejszy deterministyczny automat skończony (DFA) taki, że i $A,B$ $\Sigma$ $M$ $A \subseteq L(M)$ $L(M) \subseteq \Sigma^*\setminus B$ ?

Innymi słowy, reprezentuje zestaw pozytywnych przykładów. Każdy ciąg musi zostać zaakceptowany przez DFA. reprezentuje zestaw negatywnych przykładów. DFA nie powinien akceptować żadnego ciągu w $A$ $A$ $B$ $B$

Czy istnieje sposób na rozwiązanie tego problemu, być może przy użyciu technik minimalizacji DFA ? Mogę sobie wyobrazić utworzenie automatu podobnego do DFA, który ma trzy rodzaje stanów: akceptuj stany, odrzucaj stany i stany „nie obchodzi” (każde wejście, które kończy się stanem „nie przejmuj się”, może być albo zaakceptowane lub odrzucone). Ale czy możemy znaleźć sposób na zminimalizowanie tego do zwykłego DFA?

Można to potraktować jako problem uczenia się DFA, biorąc pod uwagę pozytywne i negatywne przykłady.

Jest to inspirowane Czy regex golf NP-Complete? , która zadaje podobne pytania o wyrażenia regularne zamiast DFA.

— DW
źródło

1

Myślę, że będziesz musiał wprowadzić pewne ograniczenia dotyczące rodzajów języków

i

oraz sposobu ich określania.

A

$A$

B

$B$

— reinierpost

Istnieje wiele literatury na temat funkcji uczenia się / języków, np. Zebranych w ramach uczenia się w limicie (także nauka w stylu Gold). Nie pasują dokładnie do Twojego problemu, ale mogą być interesujące.

— Raphael

7

Opisany DFA nazywa się DFA oddzielającym . Istnieje literatura na ten temat, gdy i są zwykłymi językami, takimi jak $A$ $B$ Nauka minimalnego oddzielania DFA dla weryfikacji kompozycyjnej, autor: Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang

Pamiętaj, że jak stwierdza @reinierpost, bez żadnych ograniczeń dotyczących A i B, problem może stać się nierozstrzygalny.

— Shaull
źródło

Jeśli oba języki A i B są zwykłymi językami i jeśli ktoś może dowolnie zaakceptować lub odrzucić dane wejściowe, dla których A i B przyniosłyby ten sam wynik, nie widzę, jak problem może być nierozstrzygalny. W przypadku DFA o dowolnym rozmiarze możliwe byłoby zbudowanie w pełni kompleksowego zestawu danych wejściowych, które powinien akceptować i danych wejściowych, które powinien odrzucić, tak aby każdy DFA o takiej samej liczbie stanów lub mniejszej, który poprawnie obsługiwałby wszystkie przypadki testowe we wszystkich przypadkach można zagwarantować identyczne zachowanie. Ponieważ maszyna, która akceptuje wszystko A akceptuje i odrzuca wszystko inne ...

— supercat

... spełniają ograniczenia, można nałożyć górną granicę liczby stanów, które musiałaby zawierać maszyna; ponieważ istnieje skończona liczba możliwych maszyn o danym rozmiarze i skończona liczba przypadków testowych do oceny, można wygenerować wszystkie możliwe maszyny, które są mniejsze niż A i sprawdzić, czy którakolwiek z nich spełnia niezbędne warunki. Nie do końca szybki sposób rozwiązania problemu, ale z pewnością rozstrzygalne, jeśli A i B są regularne. Jeśli nie są regularne, DFA nie byłby w stanie rozwiązać A lub B. „Różnica” może czasami być regularna, nawet jeśli A i B nie są, ale to ...

— supercat

... byłby to „niezwykły” przypadek.

— supercat

8

$A$ $B$ $A \cap B = \emptyset$ $A$ $A \cap B \neq \emptyset$ to oczywiście nie ma takiego DFA.

Znalezienie minimalnego DFA zgodnego z danym zestawem ciągów jest NP-zakończone. Wynik ten pojawia się jako twierdzenie 1 w pracy Angluina o złożoności wnioskowania minimalnego zbiorów regularnych . Tak wyraźnie twój problem jest również NP-zupełny.

Na wiele dobrych linków i dyskusji na temat nauki języków regularnych sprawdzeniu CSTheory blogpost na nauce języków regularnych .

— alt
źródło

Jeśli wymagania zostały zmienione, aby automat mógł arbitralnie zaakceptować lub odrzucić wszystko, co znajduje się zarówno w A, jak i B, wówczas problem zawsze można rozwiązać dla dowolnego A i B; jeśli znalezienie optymalnego automatu byłoby NP-zupełne bez zrobienia tego, byłoby NP-kompletne nawet z tym wymogiem.

— supercat