No quadro de aprendizagem autômatos de Angluin , um estudante objetivos de aprender uma linguagem regular , pedindo dois tipos de perguntas para o professor:
Consultas de palavras: dado , ?
Consultas de equivalência: dado um idioma , é ? Se não, o professor dá um contra, ou seja, uma palavra .
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.
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?
fonte