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

22

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.

mtanti
la source
Notez qu'il existe de nombreux types de grammaires au-delà des classiques de Chomsky, par exemple des grammaires sans contexte multiples , couplées et dépendantes de la longueur , respectivement (facilement googlables).
Raphael
Trouvé un tableau Wikipédia
Anton

Réponses:

14

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(baa), le plus grand point fixe est(baa)ω. Notez qu'une telle définition peut également être écrite sous forme de calcul ou derègle d'inférence:a εLwLawLawLbawLa
    (baa)(baa)ω
    aε,waw,awbawa

  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 NDw={1,,n}Pa:D{0,1}Pa(i)wi=aaΣ<<Nlimité à 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 alorsDwsuc:Dw×Dw{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(baa). Leω-language(baa)ω correspondantest décrit par laformule LTLaSwi.j. (Pb(i)  suc(i,j))¬Pb(j);a
    (baa)ω(baa)ω
    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.a(Pb(¬Pb))a
    ω

  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ΣX={x1,x2,}p(ΣX)+H={σσ:XΣ}p
    Notez queσest étendu pour travailler sur des motifs; les symboles des terminaux restent inchangés. À titre d'exemple, considéronsL(x1abbax1)={wabbaww{a,b}}.aL(p)={σ(p)σH}.a
    σ
    L(x1abbax1)={wabbaww{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 .

Raphael
la source
5

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 .

Riccardo T.
la source
5

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
Anton
la source
Et toutes les autres classes de langue?
Raphael
Et les langues sans classe?
Dave Clarke
Chomsky ne dit pas que ce sont les seuls types de langues - ce ne sont que quatre types qu'il trouve importants, et nous les trouvons toujours importants, mais il existe de nombreux autres types.
reinierpost
5

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.

Sam Jones
la source