Existe-t-il d'autres façons de décrire les langages formels que les grammaires?

Je recherche des théories mathématiques qui traitent de la description des langages formels (ensemble de chaînes) en général et pas seulement des hiérarchies grammaticales.

Les possibilités sont nombreuses. D'autres ont déjà mentionné les automates qui offrent une riche sélection. Considérez également les cadres suivants:

1. Certains langages peuvent être définis directement par des définitions (co) inductives . Par exemple, le plus petit point fixe de
   est le même langage que celui décrit par(ba∣a)∗, le plus grand point fixe est(ba∣a)ω. Notez qu'une telle définition peut également être écrite sous forme de calcul ou derègle d'inférence:$\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. Les mots définissent des structures de mots qui peuvent être utilisées comme modèles de formule logique . Essentiellement, chaque mot définit le domaine de ses positions , les prédicats P a : D → { 0 , 1 } de sorte que P a ( i ) ⟺ w i = a pour tout a ∈ Σ , un prédicat < qui est < de $D_w = \{1, \dots, n\}$$P_a : D \to \{0,1\}$$P_a(i) \Longleftrightarrow w_i = a$$a \in \Sigma$$<$$<$$\mathbb{N}$limité à et un prédicat succ : D w × D w → { 0 , 1 } qui est vrai si et seulement si le deuxième paramètre est le successeur direct du poing. Ainsi, par exemple, si w = a a b a b a a b alors$D_w$$\operatorname{suc} : D_w \times D_w \to \{0,1\}$
   $w = aababaab$
   en fait, cetteformule de premier ordredéfinit --- via l'ensemble de toutes les structures de mots qui la remplissent --- la même langue que(ba∣a)∗. Leω-language(ba∣a)ω correspondantest décrit par laformule LTL$\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*}$
   $(ba\mid a)^*$$\omega$$(ba\mid a)^\omega$
   Plusieurs équivalences entre les classes de langues classiques et certaines logiques sont connues. Par exemple,FOcorrespond àlangues sans étoile, faibleMSOaux langues régulières etMSOàwlangues réguliers réguliers. Voiricipour les références.$\qquad \begin{align*} \phantom{a}\\ \square\,(P_b \to\bigcirc(\lnot P_b)) \\ \phantom{a} \end{align*}$
   $\omega$

3. Quelque chose d'orthogonal aux classes classiques sont les langages de modèle . Supposons un alphabet terminal et un alphabet variable X = { x 1 , x 2 , … } . Une chaîne p ∈ ( Σ ∪ X ) + est appelée motif . Soit H = { σ ∣ σ : X → Σ ∗ } l'ensemble des substitutions. Nous définissons le langage d'un motif p comme$\Sigma$$X=\{x_1, x_2,\dots\}$$p \in (\Sigma \cup X)^+$$\mathcal{H}= \{\sigma \mid \sigma : X \to \Sigma^*\}$$p$
   Notez queσest étendu pour travailler sur des motifs; les symboles des terminaux restent inchangés. À titre d'exemple, considéronsL(x1abbax1)={wabbaw∣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\}^*\}$
   Notez que nous autorisons les substitutions à supprimer des variables; certaines propriétés de la classe des langages de modèles sont extrêmement différentes pour les substitutions de suppression et non de suppression. Les langages à motifs sont particulièrement intéressants dans l' apprentissage de type Gold .

Vous devriez jeter un œil à la théorie des automates . Il y a beaucoup de matériel à ce sujet.

Par exemple, vous pouvez définir un langage régulier avec un automate fini non déterministe avec des bords étiquetés: une chaîne appartient au langage si l'automate peut suivre les transitions étiquetées par ses caractères et s'arrête dans un état final.

En outre, une grammaire sans contexte peut être reconnue par un automate de refoulement .

Une autre façon de définir les langages est d' utiliser les machines de Turing .

La hiérarchie de Chomsky comprend quatre types de langages formels (chacun d'eux est un sous-ensemble de ceux qui le suivent):

Un langage formel régulier peut être décrit par:

1. Grammaire régulière
2. Automate fini (déterministe / non déterministe)
3. Expression régulière

1., 2. et 3. sont équivalents et à partir de l'un d'eux, vous pouvez construire les autres.

Un langage formel sans contexte peut être décrit par:

1. Grammaire sans contexte
2. Automate de refoulement

Aussi 1. et 2. sont équivalents.

Un langage formel contextuel peut être décrit par:

1. Automate borné linéaire (machine de Turing avec bande restreinte)

UNE langage formel récursivement énumérable peut être décrit par:

1. Machine de Turing totale

Suite aux autres réponses, on peut décrire et classer les langages en termes de "générateurs" et de propriétés de fermeture. Par exemple, il est logique de parler du plus petit AFL généré par une langue. Un bon endroit pour commencer à en apprendre davantage sur ce type de description est ce livre, bien qu'il puisse être assez difficile d'en trouver une copie papier.