Automatize o aprendizado sem contra-exemplos

13

No quadro de aprendizagem autômatos de Angluin , um estudante objetivos de aprender uma linguagem regular euΣ , pedindo dois tipos de perguntas para o professor:

Consultas de palavras: dado , ?WΣWeu

Consultas de equivalência: dado um idioma , é ? Se não, o professor dá um contra, ou seja, uma palavra .KΣK=euWKeueuK

Usando o algoritmo de Angluin, o aluno aprende com polinomialmente muitas consultas no número de estados do DFA mínimo de e no tamanho dos contra-exemplos.eueu

Agora, considere um cenário restrito em que o professor não dê mais contra-exemplos. Ainda é possível aprender L com um número polinomial de consultas? Suponho que esse não seja o caso, pois para cada sequência de perguntas e respostas de comprimento polinomial, é possível encontrar várias linguagens regulares consistentes com as respostas.

Alguém vê como provar isso?

user49692
fonte

Respostas:

20

W{0 0,1}nMW{W}2n-1

n+1M

Aryeh
fonte
1

Mark Gold de fato provou essa afirmação em seu artigo seminal "Identificação da linguagem no limite". Este é um resultado bastante conhecido agora. Você pode encontrar mais sobre isso no livro de Colin de La Higuera sobre Inferência Gramatical.

Roman Manevich
fonte