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

12

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ΣALB(Σ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 AA={ab,aaab,aaaaabb}B={b,aab,aaaba}L={a2i+1bj | i,jN}Ae são consistentes com L , ou eu posso ter um idioma completamente diferente.BL

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)?ABLLAB

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.

Francisco Mota
fonte
2
A resposta bem escrita de Lev à pergunta que eu vinculei já cobre a falta de aproximação.
Tsuyoshi Ito
6
Também escrevi uma postagem de blog com mais detalhes do que minha resposta original cstheory.blogoverflow.com/2011/08/on-learning-regular-languages
Lev Reyzin
1
Não vejo a diferença entre "sua versão" e o resultado de inadequação Lev citado na resposta. Além disso, não vejo a conexão entre "sua versão" e "indo para o outro lado".
Tsuyoshi Ito
1
AB

Respostas:

0

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

uvxΣuxAvxBABuv

AB

Denis
fonte
-1

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

vzn
fonte
1
seu segundo link apenas vincula a esta pergunta. Onde é suposto ligar?
Artem Kaznatcheev
oops, thx, corrigido
vzn 14/05