Hierarchien in regulären Sprachen

14

Gibt es eine bekannte "nette" Hierarchie L0L1L2 (kann endlich sein) innerhalb der Klasse der regulären Sprachen L ? Die Klassen in jeder Hierarchie zeichnen sich durch unterschiedliche Ausdruckskraft / Kraft / Komplexität aus. Außerdem wird die Zugehörigkeit zu jeder Klasse durch einige Elemente "gut" demonstriert (im Gegensatz zu Sternhöhenproblemen, die problematisch sein können).

Vielen Dank!

raja.damanik
quelle
3
Eine natürliche Hierarchie ergibt sich aus der Anzahl der Zustände.
Marzio De Biasi
9
Die kanonische ist die Punkttiefenhierarchie, die durch Quantifiziererwechsel in FO (<) gekennzeichnet ist. Grundsätzlich erhalten Sie durch (Boolesches Schließen von) Quantifiziererwechsel robuste Klassen und Hierarchien.
Michaël Cadilhac
Beides scheint mir eine sehr gute Antwort zu sein ...
Joshua Grochow
4
Es gibt auch Sternhöhe .
Reinierpost
Was meinst du mit einer "netten" Hierarchie im Vergleich zu "die Zugehörigkeit zu jeder Klasse wird durch einige Elemente" schön "demonstriert?" Außerhalb der regulären Sprachen scheint die Polynomhierarchie trotz der Tatsache, dass die Zugehörigkeit und die Zugehörigkeit zu einer netten Hierarchie zu sein Selbst die Existenz einer echten Hierarchie muss noch bewiesen werden
J.-E. Pin

Antworten:

15

Hier finden Sie eine Liste einiger interessanter Hierarchien, von denen einige bereits in anderen Antworten erwähnt wurden.

  1. Verkettungshierarchien

Eine Sprache ist ein gekennzeichnetes Produkt von L 0 , L 1 , ... , L n , wenn L = L 0 a 1 L 1a n L n für einige Buchstaben a 1 ,LL0,L1,,LnL=L0a1L1anLn . Verkettungshierarchien werden durch abwechselnde Boolesche Operationen und Polynomoperationen (= Vereinigung und markiertes Produkt) definiert. Die Straubing-Thérien-Hierarchie (Ausgangspunkt { , A } )a1,,an{,A}) und die Punkttiefenhierarchie (Startpunkt sind von diesem Typ, Sie können jedoch auch andere Startpunkte verwenden, insbesondere die Gruppensprachen (Sprachen, die von einem Permutationsautomaten akzeptiert werden).{,{1},A+,A}) 

  1. Sternhöhen-Hierarchien

Das allgemeine Muster besteht darin, die minimale Anzahl geschachtelter Sterne zu zählen, die erforderlich sind, um eine Sprache ab den Buchstaben auszudrücken. Abhängig von den von Ihnen zugelassenen Grundoperatoren sind jedoch mehrere Varianten möglich. Wenn Sie nur Vereinigung und Produkt zulassen, definieren Sie die eingeschränkte Sternhöhe, wenn Sie Vereinigung, Ergänzung und Produkt zulassen, definieren Sie die (verallgemeinerte) Sternhöhe und wenn Sie Vereinigung, Schnittmenge und Produkt zulassen, definieren Sie die mittlere Sternhöhe . Es gibt Sprachen mit eingeschränktem SternFür jedes n n, mit denen die Sternhöhe einer bestimmten regulären Sprache effektiv berechnet werden kann. Für die Sternhöhe ist die Sternhöhe 0 bestimmbar (sternfreie Sprachen), es existieren Sprachen der Sternhöhe 1nn01, aber es ist keine Sprache der Sternhöhe bekannt! Über die mittlere Sternhöhe ist kein Ergebnis bekannt. In diesem Dokument finden Sie eine Übersicht.2

  1. Logische Hierarchien

Es gibt viele von ihnen, aber einer der wichtigsten ist die sogenannte Hierarchie. Eine Formel , die ein zu Σ n -Formel , wenn sie eine Formel der Form entsprechen Q ( x 1 , . . . , X K ) φ , wo φ ist quantifier frei und Q ( x 1 , . . . , X k ) ist eine Folge von nΣnΣnQ(x1,...,xk)φφQ(x1,...,xk)nnur Existenzquantoren (Beachten Sie, dass dieser erste Block leer sein kann) enthält Blöcke von Quantifizierer , so daß der erste Block, der zweite Block Allzeichen usw. Und falls aus gebildet n Wenn wir die Blöcke von Quantifizierern abwechseln, die mit einem Block von Universalquantifizierern beginnen (die wiederum leer sein könnten), sagen wir, dass φ eine Π n -Formel ist. Bezeichnen Sie mit Σ n (bzw. Π n ) die Klasse der Sprachen, die durch eine Σ n -Formel definiert werden können (bzw. a ΠQ(x1,...,xk)nφΠnΣnΠnΣn -Formel) und nach B Σ n der boolesche Abschluss von Σ n -Sprachen. Schließlich sei Δ n = Σ nΠ n . Das allgemeine Bild sieht so aus. Man muss natürlich die Signatur angeben. Normalerweise gibt esfür jeden Buchstabenein Prädikat a (und ein x bedeutet, dass ein Buchstabe a an der Position x im Wort steht). Dann kann man ein binäres Symbol < hinzufügenΠnBΣnΣnΔn=ΣnΠnBildbeschreibung hier eingebenaaxax<(die entsprechende Hierarchie ist die Straubing-Thérien-Hierarchie) und auch ein Nachfolgesymbol (die entsprechende Hierarchie ist die Punkttiefenhierarchie). Andere Möglichkeiten sind ein Prädikat, Modulo zu zählen n usw. Siehe auch in dieses Papier für einen Überblick.Modn

  1. Boolesche Hierarchien

Das allgemeine Muster (das nicht spezifisch für reguläre Sprachen ist) geht auf Hausdorff zurück. Es sei eine Klasse von Sprachen, die die leere Menge und die vollständige Menge enthält und unter endlicher Überschneidung und endlicher Vereinigung geschlossen ist. Sei D n ( L ) die Klasse aller Sprachen der Form X = X 1 - X 2 + ± X n, wobei X iL und X 1X 2XLDn(L)

X=X1X2+±Xn
XiL . Schon seitX1X2X3Xn, die Klassen D n ( L ) definiereneine Hierarchie und ihre Vereinigung ist die Boolesche Schließung von L . Auch hier sind verschiedene Ansatzpunkte möglich.Dn(L)Dn+1(L)Dn(L)L
  1. Komplexität der Gruppe

Ein Ergebnis von Krohn-Rhodes (1966) besagt, dass jeder DFA durch eine Kaskade von Reset-Automaten (auch Flip-Flop-Automaten genannt) und Automaten simuliert werden kann, deren Übergangshalbgruppen endliche Gruppen sind. Die Gruppenkomplexität einer Sprache ist die geringste Anzahl von Gruppen, die an einer solchen Zerlegung des minimalen DFA der Sprache beteiligt sind. Sprachen der Komplexität sind genau die sternlosen Sprachen und es gibt Sprachen beliebiger Komplexität. Eine effektive Charakterisierung der Sprachen der Komplexität 1 ist jedoch nicht bekannt.01

  1. Von der Schaltungskomplexität geerbte Hierarchien

Ausgangspunkt ist der schöne Artikel der insbesondere zeigt, dass die Klasse A C 0R e g bestimmbar ist. Lassen A C C ( q ) = { L { 0 , 1 } * | L A C 0 M O D q } , wobei M O D q = { u { 0 , 1 }[1]AC0RegACC(q)={L{0,1}LAC0MODq} . Wenn q q ' teilt, dann ist A C C ( q ) A C C ( q ' ) . Eine interessante Frage istzu wissenob A C C ( q ) R e g entscheidbar ist für jeden q .MODq={u{0,1}|u|10modq}qqACC(q)ACC(q)ACC(q)Regq

Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Reguläre Sprachen in N C 1[1]NC1. J. Comput. System Sci. 44 (1992)

J.-E. Pin
quelle
12

Expanding the comment: a natural hierarchy is the one induced by the number of states of the DFA.

We can define Ln={L exists an n-states DFA D s.t. L(D)=L}

D={Q,Σ,δ,q0,F}|Q|=n

LnLn+1

LnLn+1Ln+1={aiin}Ln+1

Very informally: the (minimum) DFA that recognizes {aiin} must be a "state chain" of length n+1 : q0aq1a...aqn, F={qn} and qnaqn (qn has a self-loop). So n+1 states are enough to accept Ln+1. But every accepting path from q0 to a final state qf which is strictly shorter than n+1 must accept some ai with i<n which doesn't belong to Ln+1, so a DFA with n or fewer states cannot accept Ln+1.

Marzio De Biasi
quelle
8

I recently came across this paper which may give another relevant example (cf. the last sentence of the abstract):

Guillaume Bonfante, Florian Deloup: The genus of regular languages.

From the abstract: The article defines and studies the genus of finite state deterministic automata (FSA) and regular languages. Indeed, a FSA can be seen as a graph for which the notion of genus arises. At the same time, a FSA has a semantics via its underlying language. It is then natural to make a connection between the languages and the notion of genus. After we introduce and justify the the notion of the genus for regular languages, [...] we build regular languages of arbitrary large genus: the notion of genus defines a proper hierarchy of regular languages.

Damiano Mazza
quelle
5

Es gibt verschiedene natürliche Hierarchien für reguläre Sprachen mit unendlichen Wörtern, die beispielsweise den Begriff "Komplexität der Sprache" vermitteln:

  • Anzahl der in einem deterministischen Paritätsautomaten benötigten Ränge
  • Wadge (oder Wagner) -Hierarchie: topologische Komplexität, ωω Ebenen.

Diese Hierarchien können für reguläre Sprachen von unendlichen Bäumen verallgemeinert werden, für die neue Hierarchien erscheinen, siehe zum Beispiel diese Antwort .

Denis
quelle