L9) Au-delà de Chomsky

Les langages faiblement context-sensitive

La hiérarchie de Chomsky présente quatre niveaux bien délimités. Mais entre le Type 2 (context-free) et le Type 1 (context-sensitive), il existe une zone intermédiaire immense — et c’est précisément là que vivent les formalismes les plus utiles pour décrire le langage naturel et la musique. Bienvenue dans le monde des langages mildly context-sensitive.

Où se situe cet article ?

Dans La hiérarchie de Chomsky, nous avons vu les quatre niveaux classiques : régulier, context-free, context-sensitive, récursivement énumérable. Dans Les grammaires context-free, nous avons exploré les CFG (Context-Free Grammars, grammaires hors-contexte) en détail — leur puissance, mais aussi leurs limites.

Cet article explore le territoire qui se situe entre les CFG et les grammaires context-sensitive. Ce n’est pas un no man’s land : c’est un espace riche, peuplé de formalismes élégants qui ont transformé la linguistique computationnelle, le traitement automatique des langues, et — comme nous le verrons — l’analyse musicale.

 

Hiérarchie classique :

  Type 3 (régulier)
    ⊂ Type 2 (context-free)
      ⊂ ??? ← NOUS SOMMES ICI
        ⊂ Type 1 (context-sensitive)
          ⊂ Type 0 (récursivement énumérable)

 

Pourquoi c’est important ?

Le langage naturel déborde des CFG

Considérons cette phrase en néerlandais :

 

Ik zag Jan Piet Marie helpen leren zwemmen.
(J'ai vu Jan aider Piet à apprendre à Marie à nager.)

 

La structure de cette phrase contient des dépendances croisées en série (cross-serial dependencies). Les sujets Jan, Piet, Marie sont liés respectivement aux verbes helpen, leren, zwemmen, dans le même ordre :

 

Jan  ──────────────── helpen
  Piet  ──────────── leren
    Marie  ──────── zwemmen

 

Ce patron — où deux séquences de longueur arbitraire doivent correspondre élément par élément — ne peut pas être capturé par une grammaire context-free. C’est un résultat démontré par Stuart Shieber en 1985 pour le suisse-allemand (un dialecte présentant les mêmes structures). Les CFG ne suffisent pas pour le langage naturel.

Mais les grammaires context-sensitive (Type 1) sont beaucoup trop puissantes : elles peuvent engendrer des langages dont le parsing (l’analyse syntaxique — déterminer si une séquence appartient au langage et en reconstituer la structure) est PSPACE-complet (une classe de complexité pour laquelle aucun algorithme efficace n’est connu en général) — bien au-delà de ce qui est utile en pratique.

En musique

La situation est analogue. Certaines structures musicales dépassent les CFG :

  • Progressions harmoniques avec dépendances à longue distance (résolution de tensions séparées par des digressions)
  • Polymétrie : superposition de patterns rythmiques dont les longueurs doivent correspondre globalement
  • Canons et fugues : la structure de copie (le sujet est reproduit à différentes voix) ressemble au langage {ww}

On a besoin de quelque chose de plus expressif que le context-free, mais de raisonnablement traitable. C’est exactement ce que fournissent les langages mildly context-sensitive.

En NLP (Natural Language Processing, traitement automatique des langues)

Aujourd’hui, la plupart des parseurs sérieux en linguistique computationnelle n’utilisent pas des CFG pures. Ils utilisent des TAG (Tree Adjoining Grammars), des CCG (Combinatory Categorial Grammars), ou des variantes de MCFG (Multiple Context-Free Grammars). Tous ces formalismes vivent dans la zone mildly context-sensitive.

L’idée en une phrase

Les langages mildly context-sensitive forment une classe de langages strictement plus puissante que les context-free mais qui reste analysable en temps polynomial, capturant exactement le degré de complexité nécessaire au langage naturel et à la musique.

Expliquons pas à pas

Le problème : ce que les CFG ne peuvent pas faire

Rappelons que les grammaires context-free peuvent engendrer le langage {aⁿbⁿ} — des séquences de a suivies du même nombre de b. La pile d’un automate à pile (une machine qui dispose d’une mémoire « dernier entré, premier sorti » en plus de ses états) permet de « compter » une chose à la fois.

Mais que se passe-t-il si on doit compter trois choses simultanément ?

Le langage {aⁿbⁿcⁿ} — par exemple abc, aabbcc, aaabbbccc — n’est pas context-free. C’est un résultat classique démontrable par le lemme de pompage (un outil mathématique qui prouve qu’un langage n’est pas context-free en montrant qu’il ne possède pas certaines propriétés de répétition que tout langage context-free doit avoir).

Décryptage :

Une grammaire context-free peut « empiler » des symboles puis les « dépiler », ce qui permet de vérifier qu’une quantité correspond à une autre (comme aⁿbⁿ). Mais elle n’a qu’une seule pile. Pour vérifier simultanément que trois quantités sont égales, il faudrait en quelque sorte « deux piles indépendantes » — et c’est exactement ce que les formalismes mildly context-sensitive fournissent (via les arbres auxiliaires des TAG ou les catégories composées des CCG).

Analogie : Imaginez un parking avec un compteur unique à l’entrée (les CFG). Chaque voiture qui entre fait +1, chaque voiture qui sort fait −1. En fin de journée, on vérifie que le compteur est à zéro : autant d’entrées que de sorties (aⁿbⁿ). Ça marche. Mais maintenant, le parking exige aussi que chaque voiture passe à la caisse avant de sortir — il faut vérifier que le nombre d’entrées, de passages en caisse et de sorties correspondent tous (aⁿbⁿcⁿ). Un seul compteur ne suffit plus : il en faut un deuxième, indépendant. Les formalismes mildly context-sensitive ajoutent ce deuxième compteur — mais pas un nombre illimité (ce serait les grammaires context-sensitive complètes, bien trop puissantes).

Les 4 critères de Joshi (1985)

En 1985, Aravind Joshi a proposé une caractérisation informelle mais influente de ce que devrait être un formalisme grammatical « juste assez puissant » pour le langage naturel. Il a identifié quatre critères qu’un formalisme mildly context-sensitive devrait satisfaire :

1. Contenir tous les langages context-free (CFL ⊂ MCS)
(CFL = Context-Free Languages, les langages engendrables par des CFG ; MCS = Mildly Context-Sensitive)

Le formalisme doit au minimum engendrer tout ce qu’une CFG peut engendrer. C’est un plancher : on veut plus, pas moins.

2. Capturer les dépendances croisées en série

Le formalisme doit pouvoir engendrer des langages comme {aⁿbⁿcⁿ} et les structures cross-serial du néerlandais et du suisse-allemand.

3. Avoir la propriété de semilinéarité (constant growth)

Décryptage :

Un langage est semilinéaire si la longueur de ses mots croît de manière « régulière » — plus précisément, si l’ensemble des vecteurs de Parikh (comptant les occurrences de chaque symbole) forme un ensemble semilinéaire. En pratique, cela exclut les langages dont la croissance est exponentielle ou erratique.

En termes simples : les mots du langage ne peuvent pas avoir des longueurs arbitrairement « capricieuses ». Si un mot de longueur 10 existe, il n’est pas possible que le prochain mot valide ait une longueur de 1000 sans qu’il y en ait entre les deux.

4. Etre analysable en temps polynomial

Le problème de parsing doit être résoluble en temps polynomial — typiquement O(n⁶) ou mieux. La notation O(n⁶) signifie que le temps de calcul croît au plus comme la sixième puissance de la longueur de l’entrée n : doubler la longueur multiplie le temps par environ 64. C’est crucial pour les applications pratiques.

Décryptage :

Les grammaires context-sensitive complètes (Type 1) sont PSPACE-complètes pour le parsing — essentiellement intractables pour des entrées de taille raisonnable. Les formalismes mildly context-sensitive gardent le parsing polynomial, ce qui les rend utilisables en pratique pour analyser des phrases ou des partitions.

Ces quatre critères ne constituent pas une définition formelle (Joshi lui-même parlait d’une « caractérisation informelle »), mais ils ont guidé la recherche pendant des décennies et se sont révélés remarquablement fructueux.

Les TAG (Tree Adjoining Grammars)

Les TAG, introduites par Joshi en 1975, sont le formalisme emblématique de la zone mildly context-sensitive. L’idée fondatrice : au lieu de réécrire des chaînes (comme les CFG), on manipule directement des arbres.

Les deux types d’arbres

Une TAG est définie par deux ensembles d’arbres élémentaires :

Arbres initiaux (alpha) : des arbres complets avec des feuilles marquées par des non-terminaux (symboles intermédiaires destinés à être remplacés, comme S, NP, VP — par opposition aux terminaux qui sont les mots concrets du résultat final) pour la substitution (notées ↓) :

 

     S                    NP
    / \                  / \
  NP↓  VP              D    N
       / \             |    |
      V   NP↓        "le" "chat"
      |
   "mange"

 

Arbres auxiliaires (beta) : des arbres avec un noeud spécial appelé pied (foot node), marqué par *, du même type que la racine :

 

      VP
     / \
   Adv   VP*
    |
  "souvent"

 

Les deux opérations

Substitution : on remplace un noeud feuille ↓ par un arbre initial du type correspondant. C’est analogue à la dérivation dans une CFG.

 

Avant :         S              Arbre NP :    NP
               / \                           / \
             NP↓  VP                        D    N
                  / \                       |    |
                 V   NP↓                  "le" "chat"
                 |
              "mange"

Après substitution de NP↓ (gauche) :

                 S
                / \
              NP    VP
             / \   / \
            D   N  V  NP↓
            |   |  |
          "le""chat""mange"

 

Adjunction : on insère un arbre auxiliaire à un noeud interne. Le sous-arbre existant est « greffé » au noeud pied (*). C’est l’opération qui donne aux TAG leur puissance supplémentaire.

 

Avant :         VP              Arbre auxiliaire :    VP
               / \                                   / \
              V   NP                               Adv   VP*
              |   |                                 |
           "mange""souris"                       "souvent"

Après adjunction à VP :

                VP
               / \
             Adv   VP
              |   / \
          "souvent"V  NP
                   |   |
                "mange""souris"

 

Décryptage :

L’adjunction est la clé de la puissance des TAG. Elle permet d’insérer du matériau au milieu d’une structure existante, pas seulement aux feuilles. C’est ce qui permet de capturer les dépendances à longue distance et les structures récursives imbriquées que les CFG ne peuvent pas exprimer.

Ce que les TAG peuvent exprimer

  • {aⁿbⁿcⁿdⁿ} — coordination de quatre compteurs
  • {ww} — le langage de copie (un mot suivi de sa copie exacte)
  • Les dépendances croisées du néerlandais/suisse-allemand

Ce que les TAG ne peuvent pas exprimer

  • {www} — triple copie. Cela dépasse la puissance des TAG.
  • Les langages dont le fan-out (nombre de composantes indépendantes à coordonner) dépasse 2.

Les TAG engendrent exactement les langages TAL (Tree Adjoining Languages), une classe strictement entre les CFL (langages context-free) et les CSL (Context-Sensitive Languages, langages context-sensitive de Type 1). TAL est aux TAG ce que CFL est aux CFG : la classe des langages engendrés par ces grammaires.

Complexité du parsing : O(n⁶) — polynomial, conforme au critère 4 de Joshi.

Les CCG (Combinatory Categorial Grammars)

Les CCG, développées principalement par Mark Steedman à partir des années 1980, adoptent une philosophie radicalement différente : pas d’arbres, pas de règles de réécriture. Tout repose sur des types (catégories) et des combinateurs.

Les catégories comme types

Chaque mot du lexique se voit attribuer une ou plusieurs catégories syntaxiques qui encodent directement comment ce mot se combine avec les autres.

Les catégories de base sont les types atomiques : S (phrase), NP (syntagme nominal), N (nom), etc.

Les catégories complexes sont construites avec les opérateurs / et \ :

  • X/Y : « je cherche un Y à ma droite pour devenir un X »
  • X\Y : « je cherche un Y à ma gauche pour devenir un X »

Décryptage :

Pensez aux catégories comme des fonctions typées. Un verbe transitif comme « mange » a la catégorie (S\NP)/NP — c’est-à-dire : « donne-moi un NP à droite, puis un NP à gauche, et je te construis un S ». Les barres obliques indiquent la direction : / cherche à droite, \ cherche à gauche.

Exemple : « Jean mange une pomme »

 

Jean      mange          une        pomme
NP    (S\NP)/NP        NP/N         N
                        ─────────── >   (application avant)
                            NP
      ──────────────────────── >        (application avant)
            S\NP
──────────────────────────────── <      (application arrière)
                S

 

Décortiquons chaque étape :

  1. une : NP/N cherche un N à droite. Elle trouve pomme : N. Application avant (>) : NP/N + N → NP. Résultat : « une pomme » est un NP.
  2. mange : (S\NP)/NP cherche un NP à droite. Elle trouve le NP « une pomme ». Application avant (>) : (S\NP)/NP + NP → S\NP. Résultat : « mange une pomme » est un S\NP (un prédicat qui cherche un sujet).
  3. S\NP cherche un NP à gauche. Elle trouve Jean : NP. Application arrière (<) : NP + S\NP → S. Résultat : « Jean mange une pomme » est un S.

Les combinateurs : au-delà de la simple application

Les CCG disposent de combinateurs supplémentaires qui leur donnent la puissance mildly context-sensitive :

Combinateur Notation Effet
Application avant X/Y + Y → X Consomme à droite
Application arrière Y + X\Y → X Consomme à gauche
Composition avant (B) X/Y + Y/Z → X/Z Chaîne deux fonctions
Composition arrière (B) Y\Z + X\Y → X\Z Chaîne à gauche
Type-raising avant (T) X → T/(T\X) Transforme un argument en fonction

Décryptage :

Sans les combinateurs de composition et de type-raising, les CCG seraient exactement aussi puissantes que les CFG. Ce sont ces opérations supplémentaires qui permettent aux CCG de capturer les dépendances croisées et les structures non context-free. L’idée vient des combinateurs de la logique combinatoire de Curry et Schoenfinkel (années 1920-1930) — un formalisme qui élimine les variables en les remplaçant par des fonctions d’ordre supérieur, précurseur du lambda-calcul.

L’équivalence surprenante

Voici l’un des résultats les plus remarquables de la théorie des langages formels. En 1994, Vijay-Shanker et Weir ont démontré que quatre formalismes développés indépendamment engendrent exactement la même classe de langages :

 

TAG  ≡  CCG  ≡  LIG  ≡  HG

 

Formalisme Auteur(s) Idée centrale
TAG (Tree Adjoining Grammars) Joshi (1975) Manipulation d’arbres + adjunction
CCG (Combinatory Categorial Grammars) Steedman (1987) Catégories typées + combinateurs
LIG (Linear Indexed Grammars) Gazdar (1988) Piles d’index sur les non-terminaux
HG (Head Grammars) Pollard (1984) Opération de wrapping (insertion d’une chaîne autour d’un élément « tête »)

Quatre approches radicalement différentes — arbres, types, piles, et têtes lexicales — qui convergent vers la même expressivité. Ce n’est pas un hasard : c’est le signe que cette classe de langages est naturelle, au sens mathématique du terme, de la même façon que les langages réguliers sont caractérisés indépendamment par les automates finis, les expressions régulières et les grammaires régulières.

Décryptage :

Cette convergence est analogue à la thèse de Church-Turing (le postulat selon lequel toute notion raisonnable de « calcul effectif » est équivalente à ce que peut faire une machine de Turing) : quand des formalismes très différents convergent vers la même notion, c’est probablement parce que cette notion capture quelque chose de fondamental. Ici, la classe TAL (Tree Adjoining Languages) semble capturer un « sweet spot » de complexité linguistique.

MCFG : la hiérarchie infinie

Les TAG et leurs équivalents ne sont qu’un point sur une échelle continue. Les MCFG (Multiple Context-Free Grammars), introduites par Seki et al. (1991), généralisent les TAG en une hiérarchie paramétrée par un entier k appelé le fan-out.

 

MCFG(1)  =  CFG                        (context-free)
MCFG(2)  =  TAG / CCG / LIG / HG       (mildly context-sensitive)
MCFG(3)  ⊃  MCFG(2)                    (peut engendrer {www})
MCFG(4)  ⊃  MCFG(3)                    (peut engendrer {wwww})
...
MCFG(k)  ⊃  MCFG(k-1)
...
Union de tous les MCFG(k) = les langages semilinéaires

 

Le fan-out k contrôle le nombre de « composantes » qu’une règle peut manipuler simultanément. Un fan-out de 1 donne les CFG classiques. Un fan-out de 2 donne exactement les TAG. Chaque incrément permet d’exprimer une copie supplémentaire.

Décryptage :

Le fan-out mesure en quelque sorte le « nombre de piles » disponibles pour le calcul. Les CFG ont une pile (fan-out 1), les TAG en ont deux (fan-out 2), et les MCFG(k) en ont k. La complexité du parsing est O(n^(3k)), donc elle reste polynomiale pour tout k fixé — mais le degré du polynôme croît.

Cela crée une échelle de Chomsky raffinée entre le Type 2 et le Type 1, avec une infinité de marches intermédiaires. La question pratique est alors : quel fan-out est nécessaire pour le langage naturel ? Le consensus actuel est que le fan-out 2 (TAG/CCG) suffit pour la grande majorité des phénomènes syntaxiques, avec peut-être un fan-out 3 ou 4 pour quelques constructions exotiques dans certaines langues.

Applications à la musique

La zone mildly context-sensitive n’est pas qu’un objet théorique pour linguistes. Elle a des applications directes et profondes en analyse musicale.

Steedman : les grammaires de jazz avec CCG

Mark Steedman (celui-là même qui a développé les CCG pour la linguistique) a appliqué son formalisme aux progressions d’accords de jazz dès les années 1980-90. L’idée : les accords ne se succèdent pas au hasard, ils obéissent à des règles de combinaison analogues à la syntaxe des langues naturelles.

Par exemple, une résolution V7 → I (accord de dominante septième vers accord de tonique — la résolution harmonique fondamentale en musique tonale) est analogue à l’application d’un argument à un verbe. Un ii-V-I (la progression sous-dominante → dominante → tonique, par exemple Dm7 → G7 → Cmaj7 en do majeur — le patron le plus courant du jazz) est une composition de fonctions harmoniques. La récursivité et les dépendances à distance (une tension posée dans une mesure et résolue bien plus tard) nécessitent un formalisme plus puissant que les CFG.

Encart : la même progression en BP3

En CCG, Steedman modélise un turnaround (séquence d’accords qui ramène à la tonique pour relancer un nouveau chorus) ii-V-I comme une composition de fonctions typées : le ii7 (catégorie (I\I)/V) « attend » un V7 à sa droite pour former un mouvement cadentiel, qui « attend » lui-même un I pour se résoudre. C’est de l’application de fonctions harmoniques.

BP3 (Bol Processor 3, logiciel de composition algorithmique fondé sur des grammaires formelles — voir I2) exprime la même structure avec une grammaire pondérée (où chaque règle a un poids numérique <n> influençant sa probabilité de sélection) et un flag (variable conditionnelle qui contrôle quelles règles peuvent s’appliquer — voir B4) :

gram#1[1] /ch=4/  |Jazz| --> |Tour| |Jazz|  /ch-1/
gram#1[2] /ch<1/  |Jazz| --> |Coda|
gram#1[3] <3>     |Tour| --> Dm7 G7 Cmaj7
gram#1[4] <2>     |Tour| --> Dm7 Db7 Cmaj7
gram#1[5] <1>     |Tour| --> Bb7 A7 Dm7 G7 Cmaj7
gram#1[6]         |Coda| --> Dm7 G7 Cmaj7 _

La règle [3] génère le turnaround classique ii-V-I (poids 3, le plus fréquent). La règle [4] utilise la substitution tritonique (remplacement d’un accord de dominante par un autre situé à un triton — trois tons — de distance : Db7 au lieu de G7, car les deux partagent les mêmes notes de tension). La règle [5] ajoute un cycle de quintes étendu (une chaîne de résolutions V→I enchaînées : Bb7→A7→Dm7→G7→Cmaj7). Le flag ch compte les chorus (les tours complets de la grille harmonique) : après 4 tours, la condition /ch<1/ déclenche la coda (section conclusive du morceau).

Là où les CCG composent des fonctions typées (le V7 « consomme » le ii7), BP3 compose des séquences pondérées avec contrôle d’état. Le résultat musical est le même ; les mécanismes formels sont différents. Les deux vivent dans la zone mildly context-sensitive — le flag ch joue un rôle analogue aux combinateurs de composition des CCG : il coordonne la structure globale au-delà du context-free.

Rohrmeier : l’harmonie tonale comme structure arborescente

Martin Rohrmeier et ses collaborateurs ont développé des modèles de l’harmonie tonale utilisant des structures arborescentes inspirées des TAG. L’idée est que les prolongements et les digressions harmoniques sont des opérations d’adjunction : on insère du matériau au milieu d’une progression structurelle, exactement comme un adverbe s’insère dans une phrase.

 

Progression basique :     I ──── V ──── I
                              (tension → résolution)

Avec adjunction :         I ── IV ── ii ── V ──── I
                              └──── adjunction ────┘

 

BP3 : positionnement dans la hiérarchie

Où se situe BP3 dans cette hiérarchie ? C’est une question subtile :

  • Sans flags : les grammaires BP3 sont essentiellement context-free (dérivation par réécriture de non-terminaux)
  • Avec flags bornés : les flags permettent de conditionner l’application des règles en fonction d’un état global fini, ce qui donne une puissance comparable aux mildly context-sensitive (TAG/CCG)
  • Avec flags non bornés (si cela était permis) : on atteindrait la puissance Turing-complète (capable de calculer tout ce qu’une machine de Turing peut calculer — le maximum théorique de puissance de calcul)

En pratique, les flags BP3 sont bornés (nombre fini de valeurs possibles), ce qui place BP3 confortablement dans la zone MCS.

 

Hiérarchie de Chomsky raffinée — positionnement de BP3 :

Type 3 (régulier)                        Automates finis
  │
Type 2 (context-free)                    CFG, automates à pile
  │   BP3 sans flags ← ici
  │
MCFG(2) = TAG/CCG (mildly CS)           Parsing O(n⁶)
  │   BP3 avec flags bornés ← ici
  │
MCFG(3), MCFG(4) ...                    Parsing O(n⁹), O(n¹²)...
  │
Type 1 (context-sensitive)               PSPACE-complet
  │
Type 0 (récursivement énumérable)        Turing-complet

 

Ce qu’il faut retenir

  1. Le gap de Chomsky : entre les langages context-free (Type 2) et context-sensitive (Type 1), il existe une zone immense et structurée — les langages mildly context-sensitive — qui capture exactement la complexité nécessaire au langage naturel et à la musique.
  2. Les critères de Joshi : un formalisme MCS doit (a) contenir les CFL, (b) capturer les dépendances croisées, (c) préserver la semilinéarité, et (d) permettre un parsing polynomial.
  3. TAG et adjunction : les Tree Adjoining Grammars manipulent des arbres avec deux opérations (substitution et adjunction). L’adjunction — insertion d’un arbre au milieu d’un autre — est la clé de leur expressivité.
  4. CCG et combinateurs : les Combinatory Categorial Grammars encodent la syntaxe dans des catégories typées combinées par des opérateurs (application, composition, type-raising).
  5. L’équivalence TAG/CCG/LIG/HG : quatre formalismes indépendants convergent vers la même classe de langages, signe qu’elle est mathématiquement naturelle.
  6. MCFG et fan-out : les MCFG(k) créent une hiérarchie infinie entre CFG et CSG (grammaires context-sensitive), paramétrée par le fan-out k. Les TAG correspondent à k = 2.
  7. En musique : Steedman et Rohrmeier utilisent CCG et TAG pour modéliser les progressions harmoniques. BP3 avec flags bornés se situe dans la zone mildly context-sensitive.

Pour aller plus loin

  • Joshi, A. (1985). « Tree Adjoining Grammars: How much context-sensitivity is required to provide reasonable structural descriptions? » in Dowty et al. (eds.), Natural Language Parsing — l’article fondateur qui pose les 4 critères et introduit la notion de mildly context-sensitive.
  • Steedman, M. (2000). The Syntactic Process. MIT Press — la référence sur les CCG, de la théorie linguistique aux applications computationnelles, avec des extensions aux grammaires musicales.
  • Kallmeyer, L. (2010). Parsing Beyond Context-Free Grammars. Springer — une introduction pédagogique accessible aux TAG, CCG, MCFG et au parsing associé. Idéal comme premier contact technique.
  • Vijay-Shanker, K. & Weir, D. (1994). « The equivalence of four extensions of context-free grammars. » Mathematical Systems Theory, 27(6) — la preuve formelle de l’équivalence TAG = CCG = LIG = HG.
  • Rohrmeier, M. (2011). « Towards a generative syntax of tonal harmony. » Journal of Mathematics and Music — application des structures arborescentes (inspirées TAG) à l’harmonie tonale.
  • Shieber, S. (1985). « Evidence against the context-freeness of natural language. » Linguistics and Philosophy — la preuve que le suisse-allemand n’est pas context-free, déclencheur de toute cette recherche.
  • Dans cette série : L1) Hiérarchie de Chomsky pour les fondations, L2) Grammaires context-free pour le point de départ.

Glossaire

  • Adjunction : opération centrale des TAG. Consiste à insérer un arbre auxiliaire à un noeud interne d’un arbre existant, en « découpant » le sous-arbre et en le rattachant au noeud pied. C’est ce qui distingue les TAG des CFG.
  • CCG (Combinatory Categorial Grammar) : formalisme grammatical où chaque mot porte une catégorie typée (comme (S\NP)/NP pour un verbe transitif) et les mots se combinent par des opérateurs (application, composition, type-raising).
  • Combinateur : opération de combinaison dans les CCG. Les principaux sont l’application (avant/arrière), la composition (B), et le type-raising (T). Ils proviennent de la logique combinatoire de Curry.
  • Cross-serial dependencies (dépendances croisées) : structure syntaxique où deux séquences d’éléments se correspondent élément par élément, comme les sujets et verbes en néerlandais (A₁ A₂ A₃ B₁ B₂ B₃ où Aᵢ dépend de Bᵢ).
  • Fan-out : paramètre des MCFG qui mesure le nombre de composantes qu’une règle peut manipuler simultanément. Fan-out 1 = CFG, fan-out 2 = TAG.
  • Mildly context-sensitive (faiblement context-sensitive) : classe de langages satisfaisant les critères de Joshi : contient les CFL, capture les dépendances croisées, est semilinéaire, et permet un parsing polynomial.
  • Parsing polynomial : algorithme d’analyse syntaxique dont le temps d’exécution est borné par un polynôme en la longueur de l’entrée. Pour les TAG : O(n⁶). Pour les CFG (algorithme CYK, Cocke-Younger-Kasami) : O(n³).
  • Semilinéarité : propriété d’un langage dont les vecteurs de Parikh (comptant les occurrences de chaque symbole) forment un ensemble semilinéaire. Intuitivement, les longueurs des mots croissent de manière régulière.
  • Substitution : opération des TAG qui remplace un noeud feuille marqué (↓) par un arbre initial du type correspondant. Analogue à la dérivation dans une CFG.
  • TAG (Tree Adjoining Grammar) : formalisme grammatical qui manipule des arbres élémentaires (initiaux et auxiliaires) via deux opérations : substitution et adjunction. Introduit par Joshi (1975).

Prérequis : La hiérarchie de Chomsky, Les grammaires context-free
Temps de lecture : 12 min
Tags : #mildly-context-sensitive #tag #ccg #hierarchie-chomsky

Article précédent : L8) Sémantique axiomatique
Prochain article : L10) Grammaires d’attributs