En el marco de aprendizaje de autómatas de Angluin , un estudiante tiene como objetivo aprender un lenguaje regular haciendo dos tipos de preguntas a su maestro:
Consultas de palabras: dado , ¿es ?
Consultas de equivalencia: dado un lenguaje , ¿es ? Si no, el profesor da un contraejemplo, es decir, una palabra .
Usando el algoritmo de Angluin, el estudiante aprende con polinomios muchas consultas en el número de estados del DFA mínimo de y el tamaño de los contraejemplos.
Ahora, considere un escenario restringido donde el maestro ya no da contraejemplos. ¿Todavía es posible aprender L con un número polinómico de consultas? Supongo que este no es el caso porque para cada secuencia de consultas y respuestas de longitud polinómica, uno puede encontrar varios idiomas regulares consistentes con las respuestas.
¿Alguien ve cómo probar esto?
fuente