Gibt es ein Analogon von "regulär" für unendliche Zeichenfolgen?

Betrachten Sie die Folge . Es scheint auf eine Weise "regelmäßig" zu sein, die z. B. nicht ist. $s_1 = (1, 0, 1, 0,\dots)$ $s_2 = (1, 2, 3, 4,\dots)$

Ich bin mir jedoch nicht sicher, wie ich diese Intuition formalisieren soll. Eine Sache, die mir auffällt, ist, dass eine reguläre Sprache ist und in gewissem Sinne die Grenze der Zeichenfolgen in dieser Sprache ist. $L =\{(0 1)^n\}$ $s_1$

Gibt es eine Terminologie für die Berücksichtigung dieser unendlichen Zeichenfolgen? Haben wir etwas Analoges zum Pump-Lemma, wobei wir sagen können, dass eine solche "unendliche reguläre" Zeichenfolge die Form mit , , endlich hat? $x y^ {\infty}z$ $x$ $y$ $z$

formal-languages regular-languages Xodarap
quelle

Vielleicht periodisch oder schließlich periodisch .

Yuval Filmus

Pumpen : Ihre Aussage über unendliche Zeichenfolgen ist kaum ein Analogon zum Pumping Lemma , das besagt, dass ausreichend lange Wörter in einer regulären Sprache einen Teilstring enthalten, der wiederholt werden kann, um ein anderes Wort zu ergeben. Es heißt nicht, dass alle Wörter diese Form haben!

PJTraill

Terminologie : Sie sprechen von einer regulären Zeichenfolge , während der Begriff " regulär" normalerweise auf Sprachen angewendet wird.

PJTraill

Antworten:

Der wahrscheinlich spezifischste Begriff zur Beschreibung Ihrer ersten Zeichenfolge, ist periodisch . Ein String (endlich oder unendlich) periodisch , wenn es etwas ist , so dass für alle , . In diesem Beispiel können wir . Eine etwas schwächere Vorstellung ist, dass eine Zeichenfolge schließlich periodisch ist, wenn es und so dass für alle . $010101\dots$ $x_1x_2\dots$ $t$ $i$ $x_i=x_{i+t}$ $t=2$ $n$ $t$ $x_i=x_{i+t}$ $i\geq n$

Im Allgemeinen gibt es jedoch ein direktes Analogon der regulären Sprachen, nämlich die regulären Sprachen . Diese werden durch natürliche Verallgemeinerungen endlicher Automaten erkannt. Die Zustandsmenge ist immer noch endlich, aber das Akzeptanzkriterium muss geändert werden, um mit unendlichen Wörtern umgehen zu können. Insbesondere können wir nicht einfach "Akzeptieren, wenn der Automat in einem akzeptierenden Zustand endet" sagen, da der Automat die Verarbeitung seiner unendlichen Eingabe nie beendet. $\omega$

Die einfachste Klasse von Automaten für unendliche Wörter sind Büchi-Automaten . Sie sind genau wie die endlichen Automaten definiert, an die Sie gewöhnt sind, und sie akzeptieren ihre Eingabe, wenn mindestens ein akzeptierender Zustand während des Laufs des Automaten unendlich oft besucht wird. Ein Unterschied zu gewöhnlichen endlichen Automaten besteht darin, dass sich herausstellt, dass nichtdeterministische Büchi-Automaten leistungsfähiger sind als deterministische, und dass die regulären Sprachen von nichtdeterministischen Büchi-Automaten akzeptiert werden. Andere sinnvolle Akzeptanzkriterien führen zu anderen Automatenmodellen, die dieselbe Klasse von Sprachen akzeptieren. $\omega$

Beachten Sie, dass es nicht ganz sinnvoll ist, zu schreiben , da Sie nach einer unendlichen Folge von s nichts mehr haben können . Zumindest können Sie nicht, wenn die Positionen in Ihrer Zeichenfolge durch die natürlichen Zahlen indiziert sind. Wenn sie durch größere Ordnungszahlen indiziert sind, kann dies sinnvoll sein. $xy^\omega z$ $y$

Ich kann mich nicht erinnern, ob es ein Analogon zum Pump-Lemma für reguläre Sprachen gibt. Das ist etwas peinlich, obwohl es fast ein Jahrzehnt her ist, seit ich eine Abschlussklasse über dieses Zeug unterrichtet habe. $\omega$

David Richerby
quelle

Nett. Fügen Sie vielleicht explizit hinzu, dass reguläre Sprachen endliche Vereinigungen von Sprachen , wobei regulär sind. Ich weiß nichts über das Pumpen, aber manchmal ist es nützlich zu beobachten, dass jede reguläre Sprache eine eventuell periodische Zeichenfolge enthalten muss.

ω

$\omega$

A B^{ω}

$AB^\omega$

A, B

$A,B$

ω

$\omega$

Hendrik

Ich habe die Standarddarstellung des Pump-Lemmas immer gehasst, weil sie so verdammt stumpf ist. Wenn man es genau betrachtet, heißt es nur, dass, da es eine endliche Menge von Zuständen gibt, jede Zeichenfolge mit mehr Symbolen als Zuständen während eines Laufs des Automaten einen Zustand zweimal besuchen muss. Die Symbole, die an dieser Schleife teilnehmen, können Sie "pumpen". In diesem Licht ist klar, dass es ein Analogon gibt, wenn wir zu unendlichen Strings übergehen, aber endliche Zustände beibehalten; Die Frage ist also nicht "Gibt es ein pumpendes Lemma?" aber "wie viel komplizierter ist das Pump-Lemma?".

Daniel Wagner

@ DanielWagner: Wow, ja ... die Standardpräsentation ist in der Tat verdammt stumpf und deine macht es deutlich. Vielen Dank für diese Erklärung!

user541686

@DanielWagner: Das Pump-Lemma ist sicherlich verwirrend, aber der Vorteil der Standarddarstellung besteht darin, dass es sich nicht auf die Mechanik von Automaten, regulären Ausdrücken oder eine andere bestimmte Art der Definition regulärer Sprachen bezieht. Es geht nur um Saiten!

Max

@ Max Ein zweifelhafter Vorteil!

Daniel Wagner

Dies ist ein grundlegendes Ergebnis der Typ-Zwei-Effektivität, das Ihrer Meinung nach Ihre Frage aus berechenbarer Sicht beantwortet. Im Folgenden bestehen unsere Sprachen nur aus unendlichen Zeichenfolgen. Wir bezeichnen die Menge der unendlichen Zeichenketten . $\Sigma^\omega$

Satz: Wenn ein realisierbarer Automat an jeder unendlichen Zeichenkette endet, ist die Sprache des Automaten gleich wobei eine endliche Menge endlicher Zeichenketten ist. $S\Sigma^\omega$ $S$

Der Beweis ist von Königs Lemma.

Die Schlussfolgerung ist, dass eine Sprache über unendliche Zeichenfolgen entweder in gewissem Sinne "einfach" (was eine interessante Tatsache ist ) oder unentscheidbar ist. Jede nicht triviale Vorstellung von Sprache über unendliche Zeichenketten ist unentscheidbar.

Sie können vermutlich weniger einfache Sprachen lernen, wenn Sie zulassen, dass die Mitgliedschaft eher halbentscheidbar als entscheidbar ist. Dies kann immer noch als "Informatik" und nicht nur als unendliche Mathematik betrachtet werden (es hat mit Suchproblemen statt mit Entscheidungsproblemen zu tun; Semidecidability ist in gewissem Sinne ausreichend, um eine Suche durchzuführen).

ogogmad
quelle