DFA mínimo que satisfaz uma visão finita de um idioma

Digamos que um tenha um idioma , mas não se sabe quais strings são realmente parte do idioma. Tudo o que se tem é uma vista finita da língua: um conjunto finito de cordas Um ⊆ L que são conhecidos por estar na língua, e um conjunto finito de cadeias B ⊆ ( Σ * ∖ G ) que são conhecidos por não ser no língua.$L \subseteq \Sigma^*$$A \subseteq L$$B \subseteq (\Sigma^* \setminus L)$

Por exemplo, digamos que eu tenho a e B = { b , a um b , um a um b um } . Eu posso ter o idioma L = { a 2 i + 1 b j | i , j ∈ N } , já que $A = \{ab, aaab, aaaaabb\}$$B = \{b, aab, aaaba\}$$L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$$A$e são consistentes com L , ou eu posso ter um idioma completamente diferente.$B$$L$

Minha pergunta é: existe uma maneira conhecida de criar um DFA (autômato finito determinístico) que aceite as seqüências de caracteres em e rejeite as seqüências de caracteres em B , com um número mínimo ou quase mínimo de estados? Qual é a complexidade desse problema? Quão bom é aproximar-se de L (supondo que L tenha uma complexidade descritiva bastante baixa e A e B sejam grandes)?$A$$B$$L$$L$$A$$B$

Pergunta original em math.stackexchange.com. Decidi republicar aqui depois de não obter respostas para a pergunta original e sem ter idéia de onde procurá-las. Se alguém pudesse me indicar uma pesquisa nessa área, seria muito apreciada.

$\mathsf{NP}$$\mathsf{P}$

$W$$L_W$$G$$L_W$

$W$$G$$W$

$W$

• Limites mais baixos para aprendizado na consulta de associação e no modelo de contra-exemplo

• Existem melhorias no algoritmo de Dana Angluin para aprender conjuntos regulares

Parece-me que você pode usar um refinamento da equivalência Myhill-Nerode para esse problema.

$u\nsim v$$x\in\Sigma$$ux\in A$$vx\in B$$A$$B$$u$$v$

$A$$B$

Eu acho que esse problema pode ter sido inexatamente formulado pelo questionador. O questionador aparentemente quer um algoritmo que generalize infinitas palavras com base em exemplos específicos de palavras finitas, usando algum tipo de indução mecanizada, ou seja, reconhecendo padrões aparentes nos exemplos.

Além de algumas pesquisas da teoria da CS citadas nos comentários, há também algumas pesquisas empíricas nessa área, por exemplo, abaixo, usando RNAs para criar FSMs a partir de exemplos. Observe que sempre é possível executar um algoritmo de minimização padrão do DFA no resultado. A biblioteca AT&T FSM é boa para trabalhar nesta área.

O questionador não é específico sobre o domínio do problema, o que pode ajudar a entender a estrutura dos exemplos e obter referências mais específicas. No entanto, um exemplo que pode ser visto são os algoritmos de IA em jogos que usam algoritmos FSM. Eu suspeito que existem alguns casos em que os FSMs são aprendidos com exemplos usando algoritmos de aprendizado.

[1] Aprendendo uma classe de grandes máquinas de estados finitos com uma rede neural recorrente C. Lee Giles, 1, BG Horne, T. Lin 1995

[2] Aprendendo FSMs com redes recorrentes de agrupamento automático por Zeng & Smyth 1993

[3] Biblioteca AT&T FSM