Während ich studiert habe, ist die Entscheidung über die Regelmäßigkeit kontextfreier Sprachen unentscheidbar.
Wir können jedoch die Regelmäßigkeit mit dem Myhill-Nerode-Theorem testen, das eine notwendige und ausreichende Bedingung liefert. Das Problem sollte also entscheidbar sein.
Wo ist mein Fehler?
Antworten:
Myhill-Nerode bietet zwar eine Charakterisierung der regulären Sprachen, aber das reicht nicht aus, um zu zeigen, dass das Problem entscheidbar ist. "Entscheidbar" bedeutet, dass es einen Algorithmus gibt (formeller eine Turing-Maschine), der für jede Eingabe beendet wird und natürlich immer die richtige Antwort gibt. In diesem Fall müssten Sie also einen Algorithmus angeben, der anhand einer Sprache als Eingabe bestimmt, ob die Myhill-Nerode-Beziehung eine endliche Anzahl von Äquivalenzklassen aufweist. Es stellt sich heraus, dass dies für kontextfreie Sprachen nicht möglich ist. Details in Ihrem bevorzugten Lehrbuch für formale Sprachen.
Wenn Sie entscheiden möchten, ob eine allgemeine Sprache regulär ist, ist eine weitere Subtilität, dass Sie vorsichtig sein müssen, was die Eingabe für Ihren Algorithmus ist. Die Eingabe muss eine endliche Zeichenfolge sein - andernfalls wäre selbst das Lesen der Eingabe ein nicht terminierender Algorithmus. Bei kontextfreien Sprachen können Sie eine Grammatik als endliche Darstellung einer unendlichen Sprache verwenden. Für allgemeinere Sprachen würden Sie ... nun, etwas allgemeineres benötigen. Letztendlich sind Sie jedoch zum Scheitern verurteilt , wenn Sie mit allen Sprachen umgehen wollen . Über jedes endliche Alphabet gibt es unzählige Sprachen, aber nur unzählige endliche Zeichenfolgen. Das heißt, Sie können unmöglich alle Sprachen mit endlichen Zeichenfolgen beschreiben. 1Daher schlägt der Versuch, einen Algorithmus zu schreiben, um festzustellen, ob beliebige Sprachen, die als Eingabe angegeben werden, regelmäßig sind, tatsächlich fehl, bevor er beginnt. Es ist nicht nur so, dass Sie den Algorithmus nicht schreiben können: Sie können nicht einmal die Eingabe schreiben!
Beachten Sie, dass dies nicht bedeutet, dass Sie als Mensch Myhill-Nerode nicht verwenden können, um festzustellen, ob Sprachen regelmäßig sind. Es bedeutet nur, dass Sie keine genauen Anweisungen aufschreiben können, um mir zu sagen , wie das geht. Irgendwann müssten solche Anweisungen so etwas wie "Und dann damit herumspielen, um zu sehen, was funktioniert" oder "Von dort aus müssen Sie es selbst herausfinden" sagen.
quelle