Automatenlernen ohne Gegenbeispiele

In Angluins Automaten-Lern-Framework möchte ein Schüler eine reguläre Sprache lernen, indem er seinem Lehrer zwei Arten von Fragen stellt:$L\subseteq \Sigma^*$

Wortabfragen: , ist ?$w\in \Sigma^*$$w\in L$

Equivalence Anfragen: Da eine Sprache , ist ? Wenn nicht, gibt der Lehrer ein Gegenbeispiel , das heißt ein Wort .$K\subseteq \Sigma^*$$K=L$$w\in K\setminus L \cup L\setminus K$

Unter Verwendung des Angluin-Algorithmus lernt der Student mit polynomisch vielen Abfragen in der Anzahl der Zustände des minimalen DFA von und der Größe der Gegenbeispiele.$L$$L$

Stellen Sie sich nun ein eingeschränktes Szenario vor, in dem der Lehrer keine Gegenbeispiele mehr gibt. Ist es noch möglich, L mit einer polynomiellen Anzahl von Abfragen zu lernen? Ich vermute, dass dies nicht der Fall ist, da für jede Folge von Abfragen und Antworten mit polynomischer Länge mehrere reguläre Sprachen gefunden werden können, die mit den Antworten übereinstimmen.

Weiß jemand, wie man das beweisen kann?

Betrachten Sie Kennwortautomaten : Für jedes $w\in\{0,1\}^n$ akzeptiert das DFA $M_w$ die Sprache $\{w\}$ . In diesem Fall ist eine Mitgliedschaftsabfrage die gleiche wie eine Äquivalenzabfrage - und natürlich benötigen Sie exponentiell viele davon, um die "Nadel im Heuhaufen" zu finden. (Dies ist auch dann der Fall, wenn der Lernende im Voraus weiß, dass der Zielautomat von dieser Form ist.) Für einen formalen Beweis könnte ein Lehrer einfach auf die ersten $2^{n}-1$ Mitgliedschafts- / Äquivalenzabfragen mit NEIN antworten und den Zielautomaten adaptiv als auswählen die einzigartige verbleibende Möglichkeit.

$n+1$$M$

Mark Gold hat genau diesen Anspruch in seiner wegweisenden Arbeit "Language Identification in the Limit" unter Beweis gestellt. Dies ist mittlerweile ein bekanntes Ergebnis. Mehr dazu finden Sie in Colin de La Higueras Buch über grammatische Folgerungen.