Es gibt viele Methoden , um zu beweisen , dass eine Sprache nicht regulär ist , aber was muss ich tun, um zu beweisen , dass einige Sprache ist regelmäßig?
Wenn mir zum Beispiel gegeben wird, dass regelmäßig ist, wie kann ich dann beweisen, dass das folgende regelmäßig ist?L '
Kann ich einen nicht deterministischen endlichen Automaten zeichnen, um dies zu beweisen?
Antworten:
Ja, wenn Sie eine der folgenden Möglichkeiten haben:
für eine Sprache ist regulär. Es gibt äquivalentere Modelle , die oben genannten sind jedoch die am häufigsten verwendeten.LL L
Es gibt auch nützliche Eigenschaften außerhalb der "rechnerischen" Welt. ist auch regelmäßig, wennL
Sie können es erstellen, indem Sie bestimmte Vorgänge für reguläre Sprachen ausführen. Diese Vorgänge sind für reguläre Sprachen geschlossen , z
und mehr oder
Im vorliegenden Beispiel haben wir eine (reguläre) Sprache als Grundlage und möchten etwas über eine davon abgeleitete Sprache sagen . Wenn wir dem ersten Ansatz folgen - konstruieren Sie ein geeignetes Modell für -, können wir jedes äquivalente Modell für annehmen, das wir uns wünschen. es wird natürlich abstrakt bleiben, da unbekannt ist. Im zweiten Ansatz können wir direkt verwenden und Schließungseigenschaften darauf anwenden, um eine Beschreibung für .L ' L ' L L L L 'L L′ L′ L L L L′
quelle
Grundlegende Methoden
Logische Methoden (oft bei der formalen Verifikation verwendet)
Fortgeschrittene Methoden
Hoch entwickelte pumpende Deckspelzen. Siehe zum Beispiel
[1] J. Jaffe, Ein notwendiges und ausreichendes Pumplemma für reguläre Sprachen, Sigact News - SIGACT 10 (1978) 48-49.
[2] A. Ehrenfeucht, R. Parikh und G. Rozenberg, Pumping Lemmas for Regular Sets, SIAM J. Comput. 10 (1981), 536 & ndash; 541.
[3] S. Varricchio, Eine Pumpbedingung für reguläre Sets, SIAM J. Comput. 26 (1997) 764-771.
Na quasi Bestellungen. Siehe
[4] W. Bucher, A. Ehrenfeucht, D. Haussler, Über die Gesamtzahl der durch Ableitungsbeziehungen erzeugten Regulatoren, Theor. Comput. Sci. 40 (1985) 131–148.
[5] M. Kunz, Regelmäßige Lösungen von Sprachungleichheiten und Brunnenquasi-Ordnungen .
Algebraische Methoden, die auf Transduktionen basieren (siehe auch Operationen zum Beibehalten regulärer Sprachen ).
quelle
Die Antwort von Ran G. enthält eine ziemlich ausführliche Auflistung der äquivalenten Modelle, mit denen reguläre Sprachen angegeben werden können (und die Liste geht weiter, Zwei-Wege-Automaten, MSO-Logik, die jedoch über den Link unter "äquivalentere Modelle" abgedeckt wird '). Und wie Raphael betont, brauchen wir ein Argument, um das Publikum davon zu überzeugen, dass die gewählte Darstellung tatsächlich richtig ist.
quelle
<some property>
quelle
quelle
Eine Sprache ist normal, wenn Sie einen Scanner schreiben können, der über beliebige Zeichenfolgen entscheidet, ob diese zur Sprache gehören oder nicht. Dabei wird nicht mehr als eine feste Menge an Speicher benötigt, dh die Erkennung kann im O (1) -Raum erfolgen.
quelle
Die Transformation regulärer Ausdrücke ist eine Möglichkeit, das Schließen unter bestimmten Operationen zu beweisen. Die zwei einfachsten Beispiele sind der Verschluss unter Umkehrung und der Verschluss unter Homomorphismus .
quelle
Eine andere Möglichkeit besteht darin, die Sprache mithilfe von Operationen aufzubauen, bei denen Sie wissen, dass sie geschlossen sind. Dies ist eine Erweiterung zum Anzeigen eines regulären Ausdrucks, da Sie über viele weitere Operationen verfügen (Umkehren der Zeichenfolge, Komplementieren, Schneiden, Herausschneiden eines Teils, Beibehalten eines Teils, Homomorphismen und inverse Homomorphismen, ...).
quelle