Minimalne DFA spełniające skończony obraz języka

Powiedzmy, że mamy język , ale nie wiemy, jakie ciągi znaków są w rzeczywistości częścią tego języka. Wszystko, co ma, to skończony widok języka: skończony zestaw ciągów A \ subseteq L , o których wiadomo, że są w języku, oraz skończony zestaw ciągów B \ subseteq (\ Sigma ^ * \ setminus L), które są znane nie być w języku.$L \subseteq \Sigma^*$$A \subseteq L$$B \subseteq (\Sigma^* \setminus L)$

Na przykład, powiedzmy, że mam i . Mogę mieć język , ponieważ i są zgodne z , lub mogę mieć całkowicie inny język.B = { b , b , b } L = { 2 i + 1 b j | i , j ∈ N } A B $A = \{ab, aaab, aaaaabb\}$$B = \{b, aab, aaaba\}$$L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$$A$$B$$L$

Moje pytanie brzmi: czy istnieje znany sposób na utworzenie DFA (deterministycznych automatów skończonych), które akceptują łańcuchy w i odrzucają łańcuchy w , z minimalną lub prawie minimalną liczbą stanów? Jaka jest złożoność tego problemu? Jak dobrze jest w przybliżeniu (zakładając, że ma dość niską złożoność opisową, a i są duże)?B L L A $A$$B$$L$$L$$A$$B$

Oryginalne pytanie na math.stackexchange.com. Postanowiłem ponownie opublikować tutaj po tym, jak nie otrzymałem odpowiedzi na pierwotne pytanie i nie mając pojęcia, gdzie ich szukać. Byłbym bardzo wdzięczny, gdyby ktoś skierował mnie w stronę badań w tej dziedzinie.

Jak już wiesz z komentarzy, znalezienie minimalnego DFA spełniającego skończony zestaw pozytywnych i negatywnych przykładów to -hard. Jednak nie wszystko stracone, jeśli zechcesz nieco zmodyfikować swój paradygmat uczenia się, możemy wrócić do .$\mathsf{NP}$$\mathsf{P}$

Załóżmy, że próbujesz nauczyć się nieznanego DFA który jest minimalny dla niektórych języków . Jeśli zezwolisz na pytania dotyczące członkostwa w wyroczni i będziesz działać jako nauczyciel, odpowiadając na następujące pytanie: Czy w związku z proponowanym DFA rozpozna ? Jeśli nie, czy możesz podać kontrprzykład?L W G L $W$$L_W$$G$$L_W$

Zauważ, że jeśli wyrocznia ma dostęp do , może porównywać do w czasie wielu, ponieważ testowanie równości między zwykłymi językami jest łatwe. Generowanie przeciw-przykładu można również wykonać w czasie wielomianowym.G $W$$G$$W$

W tych ramach możesz nauczyć się w czasie wielomianowym za pomocą algorytmu Angluina ( 1987 ; pdf ) (lub udoskonalenia go przez Schapire'a ; patrz rozdział 5.4.5). Aby uzyskać więcej informacji o tym modelu, oto dwa pytania na temat cstheory i CS.SE na ten temat:$W$

• Dolne granice uczenia się w zapytaniu o członkostwo i modelu kontrprzykładowym

• Czy istnieją ulepszenia algorytmu Dany Angluin do uczenia się regularnych zestawów

Wydaje mi się, że można zastosować udoskonalenie równoważności Myhill-Nerode dla tego problemu.

Można określić jeśli istnieje , tak że a . Oznacza to, że każdy automat oddzielający od musi znajdować się w różnych stanach po odczytaniu i .$u\nsim v$$x\in\Sigma$$ux\in A$$vx\in B$$A$$B$$u$$v$

Wystarczy zbadać tę relację nad prefiksów elementów i . To da ci dolną granicę liczby potrzebnych stanów. Nie jestem pewien, czy bezpośrednio daje to sposób na zbudowanie minimalnego automatu, ale jest to przynajmniej ścieżka do eksploracji.$A$$B$

Myślę, że ten problem mógł zostać niedokładnie sformułowany przez pytającego. Pytający najwyraźniej chce algorytmu, który uogólnia nieskończone słowa na podstawie konkretnych przykładów słów skończonych, wykorzystując pewien rodzaj mechanizacji indukcji, tj. Rozpoznając pozorne wzorce w przykładach.

Oprócz niektórych badań teorii CS cytowanych w komentarzach, istnieje również więcej badań empirycznych w tej dziedzinie, np. Poniżej, z wykorzystaniem ANN do tworzenia FSM na podstawie przykładów. Uwaga: zawsze można uruchomić standardowy algorytm minimalizacji DFA na wyniku. Biblioteka AT&T FSM jest dobra do pracy w tym obszarze.

Pytający nie określa konkretnie swojej dziedziny problemów, co może pomóc w zrozumieniu struktury przykładów i uzyskać bardziej szczegółowe odniesienia. Jednak jednym z przykładów, które można zobaczyć, są algorytmy AI w grach wykorzystujących algorytmy FSM. Podejrzewam, że istnieją przypadki, w których FSM uczy się na podstawie przykładów z wykorzystaniem algorytmów uczenia się.

[1] Nauka klasy dużych skończonych maszyn stanów z nawracającą siecią neuronową C. Lee Giles, 1, BG Horne, T. Lin 1995

[2] Uczenie się FSM z samoklastrującymi sieciami cyklicznymi przez Zeng & Smyth 1993

[3] Biblioteka AT&T FSM