Hierarchien in regulären Sprachen

Gibt es eine bekannte "nette" Hierarchie $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (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!

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 1 ⋯ a n L n für einige Buchstaben a 1$L$$L_0, L_1, \ldots, L_n$$L = L_0a_1L_1 \cdots a_nL_n$ . Verkettungshierarchien werden durch abwechselnde Boolesche Operationen und Polynomoperationen (= Vereinigung und markiertes Produkt) definiert. Die Straubing-Thérien-Hierarchie (Ausgangspunkt { ∅ , A ∗ } $a_1, \ldots, a_n$$\{\emptyset, 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).$\{\emptyset, \{1\}, A^+, A^*\})\ $

2. 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$n$$n$$0$$1$, 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$

3. 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 $\Sigma_n$$\Sigma_n$$Q(x_1,...,x_k)\varphi$$\varphi$$Q(x_1,...,x_k)$$n$nur 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(x_1,...,x_k)$$n$$\varphi$$\Pi_n$$\Sigma_n$$\Pi_n$$\Sigma_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$\Pi_n$$\mathcal{B}\Sigma_n$$\Sigma_n$$\Delta_n = \Sigma_n \cap \Pi_n$$\mathbf{a}$$\mathbf{a}x$$a$$x$$<$(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.$Mod$$n$

4. 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 i ≤ L und X 1 ≤ X 2 ≤ $\mathcal{L}$$\mathcal{D}_n(\mathcal{L})$

$$\begin{equation} X = X_1 - X_2 + \cdots \pm X_n \end{equation}$$ $X_i\in \mathcal{L}$ . Schon seit$X_1 \supseteq X_2\supseteq X_3 \supseteq \cdots \supseteq X_n$, die Klassen D n ( L ) definiereneine Hierarchie und ihre Vereinigung ist die Boolesche Schließung von L . Auch hier sind verschiedene Ansatzpunkte möglich.$\mathcal{D}_n(\mathcal{L}) \subseteq \mathcal{D}_{n+1}(\mathcal{L})$$\mathcal{D}_n(\mathcal{L})$$\mathcal{L}$

5. 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.$0$$1$

6. Von der Schaltungskomplexität geerbte Hierarchien

Ausgangspunkt ist der schöne Artikel der insbesondere zeigt, dass die Klasse A C 0 ∩ R 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]$$AC^0 \cap Reg$$ACC(q) = \{ L \subseteq \{0,1\}^* \mid L \leqslant_{AC^0} MOD_q\}$ . 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 .$MOD_q = \{u \in \{0,1\}^* \mid |u|_1 \equiv 0 \bmod q\}$$q$$q'$$ACC(q) \subseteq ACC(q')$$ACC(q) \cap Reg$$q$

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

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

We can define $\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$

$D = \{Q, \Sigma, \delta, q_0, F \}$$|Q| = n$

$\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$

$\mathcal{L}_n \subsetneq \mathcal{L}_{n+1}$$L_{n+1} = \{ a^{i} \mid i \geq n \} \in \mathcal{L}_{n+1}$

Very informally: the (minimum) DFA that recognizes $\{ a^{i} \mid i \geq n \}$ must be a "state chain" of length $n+1$ : $q_0 \to^a q_1 \to^a ... \to^a q_n$, $F = \{q_n\}$ and $q_n \to^a q_n$ ($q_n$ has a self-loop). So $n+1$ states are enough to accept $L_{n+1}$. But every accepting path from $q_0$ to a final state $q_f$ which is strictly shorter than $n+1$ must accept some $a^{i}$ with $i < n$ which doesn't belong to $L_{n+1}$, so a DFA with $n$ or fewer states cannot accept $L_{n+1}$.

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.

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, $\omega^\omega$ 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 .