Gibt es andere Möglichkeiten, formale Sprachen als Grammatiken zu beschreiben?

Ich suche nach mathematischen Theorien, die sich mit der Beschreibung formaler Sprachen (Mengen von Zeichenfolgen) im Allgemeinen befassen und nicht nur mit Grammatikhierarchien.

Möglichkeiten gibt es genug. Andere haben bereits Automaten erwähnt, die eine reiche Auswahl bieten. Berücksichtigen Sie auch die folgenden Frameworks:

1. Einige Sprachen können direkt durch (co) induktive Definitionen definiert werden . Zum Beispiel, der kleinste Fixpunkt von ist dieselbe Sprache wie die von , der größte Fixpunkt ist . Beachten Sie, dass eine solche Definition auch in Form von Berechnungs- oder Folgerungsregeln geschrieben werden kann:
   (Ba|a)*(ba|a)$\qquad \begin{align*} \phantom{a} \\ &\phantom{\Rightarrow}\ \varepsilon \in L \\ w \in L &\Rightarrow aw \in L \\ aw \in L &\Rightarrow baw \in L \\ \phantom{a} \end{align*}$
   $(ba\mid a)^*$$(ba\mid a)^\omega$
   $\qquad \begin{align*} \phantom{a}\\ \frac{}{\varepsilon}, \quad \frac{w}{aw}, \quad \frac{aw}{baw} \\ \phantom{a} \end{align*}$

2. Wörter definieren Wortstrukturen , die als Modelle für logische Formeln verwendet werden können . Im Wesentlichen definiert jedes Wort die Domäne seiner Positionen und so dass für alle , ein Prädikat das von auf und ein Prädikat , das genau dann zutrifft, wenn Der zweite Parameter ist der direkte Nachfolger der Faust. Also zum Beispiel, wenn dannP a : D → { 0 , 1 } P a ( i ) ⟺ w i = a a ∈ & Sigma; < < N D w suc : D w × D w → { 0 , 1 } w = a a b a b a a $D_w = \{1, \dots, n\}$$P_a : D \to \{0,1\}$$P_a(i) \Longleftrightarrow w_i = a$$a \in \Sigma$$<$$<$$\mathbb{N}$$D_w$$\operatorname{suc} : D_w \times D_w \to \{0,1\}$
   $w = aababaab$
   (ba|a)*ω(ba|a)$\qquad \begin{align*} \phantom{a}\\ S_w \models \forall\, i. \forall\, j.\ (P_b(i)\ \land\ \operatorname{suc}(i,j)) \to \lnot P_b(j); \\ \phantom{a} \end{align*}$
   Tatsächlich definiert diese Formel erster Ordnung über die Menge aller Wortstrukturen, die sie erfüllen, die gleiche Sprache wie . Die entsprechende -Sprache wird durch die beschriebene LTL Formel Es sind verschiedene Äquivalenzen zwischen klassischen Sprachklassen und bestimmten Logiken bekannt. Zum Beispiel entspricht FO sternlosen Sprachen, schwacher MSO$(ba\mid a)^*$$\omega$$(ba\mid a)^\omega$
   $\qquad \begin{align*} \phantom{a}\\ \square\,(P_b \to\bigcirc(\lnot P_b)) \\ \phantom{a} \end{align*}$
   zu regulären Sprachen und MSO zu regulären Sprachen. Referenzen finden Sie hier .$\omega$

3. Etwas Orthogonales zu klassischen Klassen sind Mustersprachen . Angenommen, ein Terminalalphabet und ein variables Alphabet . Eine Zeichenfolge wird als Muster bezeichnet . Lassen Sie die Menge der Ersetzungen. Wir definieren die Sprache eines Musters als Beachten Sie, dass für die Bearbeitung von Mustern erweitert wurde. Terminalsymbole bleiben unverändert. Als Beispiel betrachtenX = { x 1 , x 2 , ... } p ∈ ( Σ ∪ X ) + H = { & sgr; | & sgr; : X → Σ * } $\Sigma$$X=\{x_1, x_2,\dots\}$$p \in (\Sigma \cup X)^+$$\mathcal{H}= \{\sigma \mid \sigma : X \to \Sigma^*\}$$p$
   σL(x1abbax1)={weinbbaw|w∈{a,b}*$\qquad \begin{align*} \phantom{a}\\ \mathcal{L}(p) = \{\sigma(p) \mid \sigma \in \mathcal{H}\}. \\ \phantom{a} \end{align*}$
   $\sigma$
   $\mathcal{L}(x_1abbax_1)= \{wabbaw\mid w \in \{a,b\}^*\}$ .
   Beachten Sie, dass Substitutionen das Löschen von Variablen zulassen. Einige Eigenschaften der Klasse der Mustersprachen unterscheiden sich erheblich beim Löschen von Ersetzungen und beim Nicht-Löschen von Ersetzungen. Mustersprachen sind beim Lernen im Goldstil von besonderem Interesse .

Sie sollten einen Blick auf die Automatentheorie werfen . Es gibt viel Material darüber.

Sie können beispielsweise eine reguläre Sprache mit einem nicht deterministischen endlichen Automaten mit beschrifteten Kanten definieren: Ein String gehört zur Sprache, wenn der Automat den Übergängen folgen kann, die durch seine Zeichen gekennzeichnet sind, und in einem Endzustand anhält.

Auch eine kontextfreie Grammatik kann von einem Pushdown-Automaten erkannt werden .

Eine andere Möglichkeit, Sprachen zu definieren, ist die Verwendung von Turing-Maschinen .

In der Chomsky-Hierarchie gibt es vier Arten formaler Sprachen (jede davon ist eine Teilmenge der folgenden Sprachen):

Eine reguläre formale Sprache kann beschrieben werden durch:

1. Regelmäßige Grammatik
2. Endlicher Automat (deterministisch / nicht deterministisch)
3. Regulären Ausdruck

1., 2. und 3. sind äquivalent und aus einem von ihnen kann man die anderen konstruieren.

Eine kontextfreie Formensprache kann beschrieben werden durch:

1. Kontextfreie Grammatik
2. Pushdown-Automat

Auch 1. und 2. sind gleichwertig.

Eine kontextsensitive Formensprache kann beschrieben werden durch:

1. Linear begrenzter Automat (Turingmaschine mit begrenztem Band)

Eine rekursiv aufzählbare formale Sprache kann beschrieben werden durch:

1. Total Turing Maschine

Zusätzlich zu den anderen Antworten kann man Sprachen in Bezug auf "Generatoren" und Schließungseigenschaften beschreiben und klassifizieren. Zum Beispiel ist es sinnvoll, über die kleinste AFL zu sprechen, die von einer Sprache erzeugt wird. Ein guter Ort, um etwas über diese Art der Beschreibung zu lernen, ist dieses Buch, obwohl es ziemlich schwierig sein kann, ein gedrucktes Exemplar zu finden.