Sternfreie Sprache vs. reguläre Sprache

11

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:

ist
Σ=¯ ist sternfrei Wenndannist Wenndannist sternfrei
AΣΣAΣ
AΣA=Σ(ΣA)Σ¯

In der letzten Zeile steht , da jedes Wort, das nicht die Form einen Buchstaben in und umgekehrt.A=Σ(ΣEIN)Σ¯EINΣEIN

Ohne Titel
quelle
AΣAΣ
reinierpost
@reinierpost Du hast die Gleichung falsch verstanden. Es gibt zwei Komplementbalken über und über der gesamten Gleichung. Entschuldigung, ich glaube, ich war 2013 nicht gut im Formatieren.EIN
Ohne Titel
@reinierpost Ich habe den Beitrag bearbeitet, um das Lesen zu erleichtern. Danke für die Rückmeldung.
Ohne Titel
Vielen Dank! Schwer zu übersehen.
Reinierpost

Antworten:

11

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.

(einein)


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

     [x.Pa(x)][x.Pa(x)[X.X(0)[x,y.X(x)suc(x,y)¬X(y)][x,y.¬X(x)suc(x,y)X(y)][x.last(x)¬X(x)]]].

    X

  4. Siehe auch hier .
Raphael
quelle
Ich weiß, was in der Logik "monadisch" ist. Wissen Sie zufällig, was die "schwache" Einschränkung ist?
Hendrik Jan
1
ω
14

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).

J.-E. Stift
quelle
7

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.

Shaull
quelle
Ja, ich meinte das Gegenteil, bearbeitete die Frage.
Ohne Titel
1

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

Holger Petersen
quelle
1
Was fügt dies der akzeptierten Antwort hinzu?
Raphael
@ Raphael Das Paritätsbeispiel. Es wäre allerdings schön, wenn Holger erklären würde, warum es nicht sternfrei ist.
David Richerby