Sternfreie Sprache vs. reguläre Sprache

Ich habe mich gefragt, ob selbst eine sternfreie Sprache ist. Gibt es eine reguläre Sprache, die keine sternfreie Sprache ist? Könnten Sie ein Beispiel geben?$a^*$

(aus Wikipdia ) Lawson definiert sternfreie Sprachen als:

Eine reguläre Sprache gilt als sternfrei, wenn sie durch einen regulären Ausdruck beschrieben werden kann, der aus den Buchstaben des Alphabets, dem leeren Satzsymbol, allen booleschen Operatoren - einschließlich Komplementation - und Verkettung, aber keinem Kleene-Stern besteht.

Hier ist der Beweis dafür, dass $a^*$ sternfrei ist:

$\emptyset$ ist$\Longrightarrow$
$\Sigma^*=\bar{\emptyset}$ ist sternfrei Wenndannist Wenndannist sternfrei$\Longrightarrow$
$A\subseteq\Sigma$$\Sigma^*A\Sigma^*$$\Longrightarrow$
$A\subseteq\Sigma$$A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$

In der letzten Zeile steht , da jedes Wort, das nicht die Form einen Buchstaben in und umgekehrt.$A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$$A^*$$\Sigma \setminus A$

Reguläre Sprachen sind solche, die durch schwache monadische Logik zweiter Ordnung (WMSO) beschrieben werden können [1].

Sternfreie Sprachen sind solche, die durch Logik erster Ordnung mit $<$ (FO [<]) [2] beschrieben werden können.

$(aa)^*$

1. Schwache arithmetische und endliche Automaten zweiter Ordnung von Büchi (1960)
2. Gegenfreie Automaten von McNaughton und Papert (1971)

3. $(aa)^*$

   $\ \begin{align} \bigl[ \forall x. P_a(x)\bigr] \land \Bigl[ \exists x. P_a(x) \to \bigl[ \exists X. X(0) &\land [\forall x,y. X(x) \land \operatorname{suc}(x,y) \to \lnot X(y)] \\ &\land [\forall x,y. \lnot X(x) \land \operatorname{suc}(x,y) \to X(y)] \\ &\land [\forall x. \operatorname{last}(x) \to \lnot X(x)] \bigr] \Bigr] \;. \end{align}$

   $X$

4. Siehe auch hier .

Schützenberger (1965) gab eine algebraische Charakterisierung der sternfreien Sprachen: Eine reguläre Sprache ist genau dann sternfrei, wenn ihr syntaktisches Monoid aperiodisch ist. Im Gegensatz zur logischen Charakterisierung (sternfrei = FO [<]) liefert diese algebraische Charakterisierung einen Algorithmus , um zu entscheiden, ob eine bestimmte reguläre Sprache sternfrei ist (die reguläre Sprache kann durch einen endlichen Automaten, einen regulären Ausdruck oder a angegeben werden reguläre Grammatik). Anhand der logischen Charakterisierung (aufgrund von McNaughton und Papert) kann man dann das folgende Problem entscheiden: Gibt es bei einer WMSO-Formel eine FO-Formel, die dieselbe Sprache beschreibt?

M.-P. Schützenberger, Über endliche Monoide mit nur trivialen Untergruppen, Information and Control 8 (1965), 190-194.

R. McNaughton und S. Papert, Counter-free automata, MIT Press, Cambridge, Mass.-London, 1971.

Ein vollständiger Beweis für Schützenbergers Theorem findet sich in verschiedenen Lehrbüchern oder Übersichtsartikeln. Eine elementare Darstellung des entsprechenden Algorithmus (ohne Beweis) finden Sie unter

J.-É. Pin, endliche Halbgruppen und erkennbare Sprachen: eine Einführung in Semigruppen, formale Sprachen und Gruppen des NATO Advanced Study Institute , J. Fountain (éd.), 1-32, Kluwer Academic Publishers, (1995).

Sternfreie Sprachen werden durch reguläre Ausdrücke beschrieben, die Verkettung, Komplementation, Vereinigung, Schnittmenge, aber keinen Kleene-Stern umfassen.

Da reguläre Sprachen bei all diesen Operationen geschlossen sind (wobei Komplementation der entscheidende Punkt ist), ist auch jede sternfreie Sprache regulär.

Vielleicht meinst du das Gegenteil? Sind alle regulären Sprachen sternfrei? Die Antwort auf Letzteres lautet nein. Weitere Informationen finden Sie in diesem Dokument.

Ein einfaches Trennungsbeispiel ist (aa) *. Anspruchsvoller: Alle binären Zeichenfolgen mit gerader (oder ungerader) Parität.