Автоматическое обучение без контрпримеров

В системе автоматического обучения Англуина ученик стремится выучить обычный язык $L\subseteq \Sigma^*$ , задавая своему учителю два типа вопросов:

Запросы по словам: если $w\in \Sigma^*$ , есть ли ?$w\in L$

Запросы на эквивалентность: если задан язык , является ли ? Если нет, то учитель дает контрпример, то есть слово .$K\subseteq \Sigma^*$$K=L$$w\in K\setminus L \cup L\setminus K$

Используя алгоритм Англуина, студент изучает с помощью полиномиального множества запросов по числу состояний минимального DFA и размеру контрпримеров.$L$$L$

Теперь рассмотрим ограниченный сценарий, когда учитель больше не дает контрпримеры. Можно ли еще узнать L с полиномиальным количеством запросов? Я предполагаю, что это не так, потому что для каждой последовательности запросов и ответов полиномиальной длины можно найти несколько регулярных языков, соответствующих ответам.

Кто-нибудь видит, как это доказать?

$w\in\{0,1\}^n$$M_w$$\{w\}$$2^{n}-1$

$n+1$$M$

Марк Голд действительно доказал это утверждение в своей оригинальной статье «Идентификация языка в пределе». Это довольно известный результат сейчас. Вы можете найти больше об этом в книге Колин де ла Хигера о грамматическом умозаключении.