Biorąc pod uwagę dwa zbiory ciągów znaków nad alfabetem Σ , czy możemy obliczyć najmniejszy deterministyczny automat skończony (DFA) M taki, że A ⊆ L ( M ) i L ( M ) ⊆ Σ ∗ ∖ B ?
Innymi słowy, reprezentuje zestaw pozytywnych przykładów. Każdy ciąg A musi zostać zaakceptowany przez DFA. B reprezentuje zestaw negatywnych przykładów. DFA nie powinien akceptować żadnego ciągu w 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.
Odpowiedzi:
Opisany DFA nazywa się DFA oddzielającym . Istnieje literatura na ten temat, gdy i B są zwykłymi językami, takimi jakA 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.
źródło
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 .
źródło