Ich habe die letzte Stunde mit diesem Problem herumgefummelt und bin unglaublich ratlos.
Sei . Zeigen Sie, dass regelmäßig ist.
Die Sprache erfüllt offensichtlich das Pumping Lemma, aber das ist für die Regelmäßigkeit nicht schlüssig. Wie um alles in der Welt beweise ich, dass diese Sprache regelmäßig ist? Ich kenne alle normalen Methoden (geschlossen usw.), kann aber für mein ganzes Leben nicht herausfinden, unter welchen Bedingungen ich fortfahren kann.
Die Sprache kann als .A = { 0 u 0 ∣ u ∈Σ∗}}
Die Grundidee ist, dass unabhängig vom Wert von alles in "absorbiert" wird, was die vollständige Sprache .k u Σ∗
quelle
Wenn es diese Sprache wäre:
Du wärst in Schwierigkeiten. ist nicht regelmäßig.B.
Das Hauptproblem besteht darin, dass Sie sich beim Erkennen von Zeichenfolgen aus eine unbegrenzte Menge an Informationen aus der anfänglichen Zeichenfolge von s "merken" müssen (wie viele es gab), da Sie zwischen Zeichenfolgen wie und solche wie (wobei ). Reguläre Ausdrücke (oder DFAs) können diese Art von "unbegrenztem Speicher" nicht ausdrücken.B. 0 0k1 ... 10k 0k1 ... 10j j ≠ k
quelle