Menor DFA que aceita seqüências de caracteres dadas e rejeita outras strings dadas

Dado dois conjuntos de cadeias sobre o alfabeto Σ , podemos calcular o menor autômato de estado finito determinístico (DFA) M de modo que A ⊆ L ( M ) e L ( M ) ⊆ Σ ∗ ∖ B ?$A,B$$\Sigma$$M$$A \subseteq L(M)$$L(M) \subseteq \Sigma^*\setminus B$

Em outras palavras, representa um conjunto de exemplos positivos. Cada sequência em A precisa ser aceita pelo DFA. B representa um conjunto de exemplos negativos. Nenhuma sequência em B deve ser aceita pelo DFA.$A$$A$$B$$B$

Existe uma maneira de resolver isso, talvez usando técnicas de minimização do DFA ? Eu poderia imaginar a criação de um autômato semelhante ao DFA que possui três tipos de estados: aceitar estados, rejeitar estados e "não se importa" (qualquer entrada que termine em um "não se importa" pode ser aceita ou rejeitado). Mas podemos encontrar uma maneira de minimizar isso para um DFA comum?

Você pode pensar nisso como o problema de aprender um DFA, dados exemplos positivos e negativos.

Isso é inspirado no regex golf NP-Complete? , que faz perguntas semelhantes para regexps em vez de DFAs.

Um DFA, como você descreve, é chamado de DFA de separação . Existe alguma literatura sobre esse problema quando e B são idiomas regulares, como Aprender DFAs mínimos de separação para verificação composicional, de Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang$A$$B$

Observe que, como afirma @reinierpost, sem restrições em A e B, o problema pode se tornar indecidível.

$A$$B$$A \cap B = \emptyset$$A$$A \cap B \neq \emptyset$

Encontrar o DFA mínimo consistente com um determinado conjunto de strings é NP-complete. Este resultado aparece como o Teorema 1 no artigo de Angluin Sobre a complexidade da inferência mínima de conjuntos regulares . Tão claramente que seu problema também é NP-completo.

Para muitos bons links e discussões sobre o aprendizado de idiomas regulares, consulte o post no blog do CSTheory Sobre o aprendizado de idiomas regulares .