Université Bordeaux Montaigne Lionel Clément
Formalisation Linguistique 1
Master RELAI–2015-2016 Département Langues et Civilisations
1 Système formel
Un système formel est un objet mathématique à deux faces. L’une est pu-
rement syntaxique. Elle dit comment les écritures du système formel sont pos-
sibles. L’autre est sémantique ; elle dit le sens de ces écritures. Les exemples
sont nombreux : logique mathématique, théorie axiomatique des ensembles,
etc.
L’intérêt d’un système formel est de permettre un raisonnement théorique
sur l’écriture et non sur le sens de ces écritures. On peut par exemple automa-
tiser le raisonnement et montrer les contradictions d’une théorie de façon re-
productible et falsifiable sans utiliser l’intuition, les croyances ou la réthorique
comme base argumentaire.
Un système formel est composé de
— Un alphabet fini de symboles
— Un procédé de construction des formules
— Un ensemble de formules axiomatiques (supposées correctes sans démontration)
— Un ensemble de règles de déduction (permettant de produire des for-
mules correctes à partir d’autres formules correctes)
Par exemple la logique propositionnelle est un système formel qui contient :
— Un ensemble de lettres (opérateurs, parenthèses, constantes, variables,
etc.)
— Un procédé de construction des formules :
— Une constante ou une variable est une formule
— Si f est une formule, alors ¬(f ) est une formule
— Si f1 et f2 sont des formules, alors (f1 → f2 ), (f1 ∧ f2 ), (f1 ∨ f2 )
sont des formules
— Un ensemble d’axiomes :
— ` x → (y → x)
— ` x → (y → z) → ((x → y) → (x → z))
— ` (¬y → ¬x) → (x → y)
— La règle de déduction modus ponens
— `x,(`x→y)
`y
Le sens donné aux formules permet de motiver les axiomes et la règle de
déduction. Les formules ont une interprétation notée φ dans {0, 1} telle que
1
— φ(¬(x)) vaut 1 − φ(x)
— φ(x → y) vaut 0 si et seulement si φ(x) = 1 et φ(x) = 0
2 Langage formel
La notion de langage formel nous permettra de modéliser des propriétés
linguistiques tels que la structure syntaxique des phrases, la morphologie, les
liens de dépendance entre les mots et les phrases, etc. Nous ne confondrons
pas les langages logiques, mathématiques, de programmation informatique
qui sont des langages formels et le langage.
Le langage formel est central et historique en logique et en informatique.
Il l’est aussi dans la technique de programmation des ordinateurs qui utilise
des langages de programmation depuis les années 1950. Il est donc natu-
rel de trouver dans la littérature mathématique et informatique les notions
d’analyse syntaxique qui servent en partie, mais pas seulement, le TAL. Nous
trouverons par exemple des résultats théoriques qui intéressent le TAL dans
le traité de théorie des langages The theory of Parsing Translation and
Compiling de Alfred V. Aho et Jeffrey D. Ullman 1972, Prentice-Hall, Inc.
Par langage formel, nous entendons des ensembles de chaines de ca-
ractères. Une chaine de caractères appartient à un langage s’il a quelque
propriété définitoire de ce langage. Cette propriété est précisément ce qu’on
appelle une grammaire.
Un point de vue proche peut être suivi à propos des langues : le langage
peut se modéliser par le fait que toutes les productions licites d’un locuteur
sont grammaticales. La capacité de langage se résume alors à la capacité
à produire les seules phrases grammaticales. Le programme de recherche
linguistique appelé le générativisme propose de décrire une langue comme
l’ensemble des productions grammaticales et de les distinguer de celles qui ne
le sont pas. Il se propose de dire qu’une grammaire est le moyen de produire
l’ensemble des séquences phoniques grammaticales et elles seules. On parle
alors de la compétence linguistique du locuteur à produire de telles séquences.
Les grammaires formelles que nous voyons dans ce chapitre permettent de
modéliser cette compétence.
Les objets que l’on tente de modéliser du langage sont des éléments qui
ne se définissent pas en propre, mais en différences. Ce sont les phonèmes,
les monèmes, les graphèmes, etc. qui n’ont d’existence linguistique que par
le fait qu’ils s’organisent pas oppositions et complémentarités.
L’objet de la formalisation qui nous intéresse ici est un flux, ou une
séquence d’éléments qui se distinguent les uns des autres en nombre fini. Nous
avons donc besoin d’une algèbre élémentaire pour construire les séquences.
2
Pour définir un langage, on se donnera deux outils : le premier est un
ensemble fini d’éléments qu’on appellera un alphabet, le second est le moyen
de mettre bout-à-bout ces éléments entre eux pour produire des séquences,
la concaténation.
2.1 Monoı̈de libre
Un langage formel est donc un ensemble de séquences de lettres. Cet en-
semble n’est pas nécessairement fini, mais les lettres sont données en nombre
fini, ainsi que la taille des séquences.
L’ensemble des lettres est appelé alphabet. Il est noté Σ. L’ensemble de
toutes les séquences de lettres est noté Σ∗ .
Les chaı̂nes de lettres se combinent entre elles grâce à la concaténation,
une relation qui associe un élément unique de Σ∗ à tout couple de Σ∗ ×
Σ∗ donné. Nous notons par la multiplication cette loi de composition. Elle
permet de définir une séquence de lettres à partir de deux autres mises bout-
à-bout. Séquenciellement elle définit toutes les suites possibles de séquences
de lettres.
La concaténation respecte deux propriétés :
1. Elle est associative
∀a, b, c ∈ Σ∗ , (ab)c = a(bc)
2. Il existe un élément neutre dans Σ pour cette loi noté . Il s’agit de
la séquence vide. Il est à la concaténation ce qu’est le un à la mul-
tiplication : un élément sans effet quand il est ajouté à une séquence
existante.
∀a ∈ Σ∗ , a = a = a
Remarquons que la concaténation n’est pas commutative, et que les séquences
de lettres n’ont pas d’inverse contrairement à ce que l’on trouve avec les
nombres et la multiplication.
Σ∗ permet de construire toutes les séquences de lettres Σ. Une telle struc-
ture algébrique s’appelle un monoı̈de libre.
La construction par induction du monoı̈de libre Σ∗ se définit ainsi :
1. ∈ Σ∗
2. Σ ⊂ Σ∗
3. Si x, y ∈ Σ∗ , alors xy ∈ Σ∗
3
2.2 Langage formel sur Σ
Toute partie d’un monoı̈de Σ∗ est un langage formel sur Σ.
On peut donc définir un langage en listant un ensemble de chaı̂nes de
lettres. Le point de vue linguistique générativiste équivalent consiste à dire
que l’ensemble des productions grammaticales d’une langue donnée est cet
ensemble. Il est cependant plus intéressant de le déterminer par les propriétés
qui lui sont propres, c’est-à-dire en définissant une grammaire.
La structure des phrases, par exemple, ce qui met en rapport les chaı̂nes
de lettres entre elles par un ensemble de lois, feront partie des ces propriétés
remarquables.
Un langage sur un alphabet Σ s’écrit
Lv = {x ∈ Σ∗ : P (x)}
où P (x) désigne les propriétés auxquelles doivent satisfaire les chaı̂nes de
lettres. La spécification de ces propriétés est ce qu’on appelle une grammaire
formelle.
Il a été proposé par Noam Chomsky en 1957 (in Structures syntaxiques)
de modéliser cette propriété par un mécanisme fini. Par ailleurs, nous rap-
pelons qu’un objet infini n’a guère de chance d’être représenté in extenso
par un mécanisme fini. La mécanisation d’un langage infini n’a donc pas de
chance d’être réalisée autrement que par induction.
3 Langage rationnel et expressions régulières
Une expression régulière est une écriture qui permet de décrire immédiatement
un motif, ou filtre pour un ensemble de chaines de caractères. L’objectif pra-
tique est d’appliquer un traitement automatisé sur des textes ou toute autre
séquence pour extraire un ensemble de chaines correspondant au motif.
Plus formellement, une expression régulière est un système formel qui
dénote un langage (dit rationnel par définition).
La syntaxe des expressions régulières est la suivante :
Soit Σ un alphabet,
— La lettre vide est une expression régulière
— Tout élément de Σ est une expression régulière
— Si X et Y sont des expressions régulières, alors (XY ) est une expres-
sion régulière
— Si X et Y sont des expressions régulières, alors (X + Y ) est une ex-
pression régulière
4
— Si X est une expression régulière, alors X ∗ est une expression régulière
La sémantique de cette notation est le langage qu’elle décrit, nous no-
tons LΣ (X) pour désigner le langage décrit par l’expression régulière X sur
l’alphabet Σ :
— LΣ () = {}
— LΣ (X + Y ) = LΣ (X) ∪ LΣ (Y )
— LΣ (XY ) = {xy ∈ Σ∗ : x ∈ LΣ (X) et y ∈ LΣ (Y )}
— LΣ (X ∗ ) = ∪i∈N LΣ (X i )
X i = XX
| {z. . . X}
i
X0 =
3.1 Langage engendré par une expression régulière
Une expression régulière dénote un langage. Ce langage est immédiatement
définit par la sémantique du système formel.
Par exemple, l’expression régulière a + b∗ c dénote le langage
{ac, abc, abbc, abbbc, abbb . . . bc, . . .}. Les mots préfixés par a, suffixés par c et
qui contiennent zéro ou plusieurs b.
3.2 Extension des expressions régulières
Pour simplifier les notation, certains ajouts sont proposés aux expressions
régulières. Ils n’étendent pas le système formel.
— X + = XX ∗
— X? = + X
— X k = XX | {z . . . X}
k
— X {i,j} = XX . . . X} + XX
| {z . . . X} + · · · + XX
| {z . . . X}
| {z
i i+1 j
— [a1 a2 . . . ak ] = a1 + a2 + · · · + ak avec ai ∈ Σ
4 Automates à nombre fini d’états
Les automates sont des objets mathématiques qui permettent de désigner
des processus discrets et finis. Les processus passent d’un état à un autre étant
donné un stimulus distingué d’autres stimuli donnés également en nombre
fini.
La machine que représente l’automate possède un nombre fini d’états
distingués les uns des autres et un ensemble fini de stimuli qui permettent
de passer d’un état à un autre sans continuité. Ni les états, ni les stimuli ne
5
méritent une définition en propre. Un état de la machine est distingué de
tous les autres états, un stimulus de tous les autres stimulus.
Les stimuli seront représentés par un alphabet fini Σ, les états par un
ensemble fini Q.
Il reste à définir une relation de transition d’état à état selon les éléments
de Σ et à dire les conditions de départ et d’arrêt de la machine pour être
complet.
4.1 Définition formelle
Un automate à nombre fini d’états est un quintuplet A = (Q, Σ, q0 , F, φ)
où
Q est un ensemble fini d’états
Σ est un alphabet fini
q0 est un élément distingué de Q, appelé état initial
F est une partie de Q, dont les éléments sont appelés états terminaux
φ est une relation, qui à tout couple (q, a) de Q × Σ, associe un élement de
Q
L’automate est dit déterministe si φ est une fonction, qui à tout couple
(q, a) de Q × Σ, associe un élément unique de Q.
L’automate est dit -automate si φ est une relation, qui à tout couple
(q, a) de Q × (Σ ∪ {}), associe un élément ou plusieurs éléments différents
de Q
4.2 Automate reconnaissant un langage
Une séquence a0 a1 a2 . . . ak de Σ∗ est reconnue par l’automate si et seule-
ment s’il existe une suite d’états (q0 , q1 , q2 , . . . , qk ) où
q0 est l’état initial
qk appartient aux états terminaux
∀i ∈ [0, k − 1], φ(qi , ai ) = qi+1
Un automate à nombre fini d’états sur un alphabet Σ permet ainsi de
décrire un ensemble de chaı̂nes de Σ∗ . Voici donc une seconde façon de décrire
un langage.
On représente graphiquement un automate comme ceci
l’état initial q0 q0
6
Un état final qi qi
a
Une transition φ(qi , a) = qj qi qj
Un automate A avec q0 comme état initial et qi comme état final
q0 A qi
4.3 Automate reconnaissant un langage régulier
A toute expression régulière, il existe un automate équivalent, c’est-à-dire
qui reconnait le même langage.
Procédons par construction inductive :
1. l’automate qui reconnaı̂t LΣ () est q0
a
2. l’automate qui reconnaı̂t LΣ (a) est q0 q1
3. Soit q1 A qi l’automate qui reconnaı̂t LΣ (A)
et q2 B qj l’automate qui reconnaı̂t LΣ (B)
7
L’automate qui reconnaı̂t LΣ (A + B) est
q1 A qi
q0 qf
q2 B qj
4. L’automate qui reconnaı̂t LΣ (AB) est
q0 q1 A qi q2 B qj qf
5. L’automate qui reconnaı̂t LΣ (A∗ ) est
q1 qi
A
4.4 Suppression des transitions vides
Pour tout automate contenant des transitions vides, il existe un automate
équivalent (qui engendre le même langage).
Voici comment le construire :
Soit un automate A = (Q, Σ, q0 , F, φ) contenant des transitions vides,
c’est-à-dire des transitions φ(qi , ) = qj . On contruit l’automate A0 = (Q, Σ, q0 , F, φ0 )
où φ0 (qi , α) = qk si
1. φ(qi , α) = qk
2. Si φ(qi , ) = qj1 , φ(qj1 , ) = qj2 , . . . φ(qjk , ) = qj , et φ(qj , α) = qk
Illustration graphique :
a
q0 q1 q2
8
q1
a
q0 a q2
4.5 Déterminisation d’un automate
Tout automate fini sans transition vide A est équivalent à un automate
déterministe fini A0 . Le principe pour construire A0 consiste à lui attribuer
comme états possibles, l’ensemble de tous les sous-ensembles des états de A.
Les transitions sont celles qui permettent de passer d’un sous ensemble à
un autre dans l’automate A.
Soit A = (Q, Σ, q0 , F, φ) un automate sans transition vide.
A0 = (Q0 , Σ, q00 , F 0 , φ0 ) se construit ainsi :
— Q0 = P(Q)
— q00 = {q0 }
— ∀qi ∈ F, qi ∈ qi0 ⇒ qi0 ∈ F 0 (un état qi0 de A0 est final s’il contient un
état final de A)
— φ0 (qi0 , α) = qj0 ⇔ ∀qi ∈ qi0 , ∀qj ∈ qj0 , φ(qi , α) = qj
Exemple :
Soit l’automate A, l’automate A0 reconnaı̂t le même langage.
d
a q3
c
q0 b
a
q4
q1 c
d
b
q2
Figure 1 – Automate A
5 Systèmes de réécriture
5.1 Grammaire formelle : grammaire de réécriture
Une grammaire formelle est définie par le quadruplet (Σ, N, R, S) où :
9
c
d
a
{q0} {q1, q3}
b
d
{q4}
{q2, q3} d
c
{q2,q4} d
c
c
{q2}
Figure 2 – Automate A0
1. Σ est un alphabet fini (on parle de symboles terminaux)
2. N est un ensemble fini de termes distincts de Σ (on parle de symboles
non terminaux)
3. S est un élément distingué de N ; le terme initial de la grammaire
4. R est une relation de réécriture {(α, β)}, où α ∈ (Σ ∪ N )∗ − {}, et
β ∈ (Σ ∪ N )∗ . On écrit α → β.
Une grammaire formelle permet de définir les éléments du langage par
une opération qui fait intervenir une succession de réécritures depuis le terme
initial jusqu’aux chaı̂nes de lettres.
Dérivation On définit une relation ⇒ entre deux éléments du monoı̈de
libre (Σ ∪ N )∗
∀µ1 , α, µ2 , β ∈ (Σ ∪ N )∗ , µ1 αµ2 ⇒µ1 βµ2
vérifiée si et seulement s’il existe une règle α → β de R
∗
On définit une dérivation par la fermeture réflexive-transitive ⇒
La fermeture réflexive-transitive d’une relation R, noté R∗ , se définit ainsi :
∀x, y ∈ E, xR∗ y si et seulement si
1. ∀x ∈ E, xR∗ x
2. ∀x, y, z ∈ E, xRy et yRz ⇒ xR∗ z
Autrement dit, tout élément se dérive vers lui-même (réflexivité), et un
élément x se dérive vers un élément z s’il se dérive vers un élément y qui se
dérive vers z (transitivité).
10
Langage engendré par une grammaire Le langage engendré par la
grammaire G, noté LG , est l’ensemble de toutes les chaı̂nes de lettres qui
dérivent de l’élément initial.
On note :
∗
LG = {α ∈ Σ∗ : S ⇒ α}
Types de grammaires
1. Les grammaires formelles les plus simples qu’on puisse imaginer sont
les grammaires rationnelles. Il s’agit de grammaires telles que les règles
sont de la forme
A→a
A → aB
(resp. A → a ou A → Ba pour les grammaires rationnelles à droite).
Avec A, B ∈ N et a ∈ Σ.
Les grammaires rationnelles permettent de décrire les langages ration-
nels tout comme les expressions régulières le font. Il est donc toujours
possible de construire un automate déterministe à nombre fini d’états
qui génère le même langage qu’une grammaire rationnelle.
2. Les grammaires qui n’ont qu’un élément de N en partie gauche sont
dites indépendantes du contexte. La dérivation µ1 αµ2 ⇒µ1 βµ2 est vérifiée
si et seulement si la règle α→β appartient à R ; ceci indépendamment
du contexte de α, c’est-à-dire indépendamment de µ1 ou de µ2 .
3. Les grammaires contextuelles sont celles qui acceptent les règles
xαy → xβy
et pour lesquelles la séquence α n’est pas plus longue que la séquence β.
Ici en revanche, une dérivation µ1 αµ2 ⇒µ1 βµ2 est vérifiée étant connus
µ1 ou µ2 .
4. Les autres grammaires sont dites non contraintes ou récursivement
énumérables. Leur seule contrainte est d’avoir une séquence non vide
en partie gauche. Elles ne nous intéressent pas ici.
6 Analyse syntaxique automatique
Nous distinguerons les reconnaisseurs automatiques des analyseurs syn-
taxiques automatiques. Les premiers disent si une séquence de lettres est un
élément du langage ou non, les seconds, en plus de cette réponse, y associent
une ou plusieurs dérivations.
11
La reconnaissance des langages a une implication théorique, mais nous
intéressera moins pour les applications du Traitement Automatique des Langues.
On peut distinguer plusieurs méthodes pour construire des analyseurs
syntaxiques.
— Ascendant – descendant
Un analyseur descendant utilise l’hypothèse que le terme initial sera
dérivé vers la séquence de lettres donnée en input à l’analyseur. Le
mécanisme tente de remplacer le terme initial S par la séquence de
termes α de la partie droite de la règle S → α. Puis récursivement,
il fait l’hypothèse que les proto-phrases 1 induites par cette hypothèse
seront elles-mêmes dérivées.
Un analyseur ascendant, au contraire, part de la séquence de lettres
jusqu’au terme initial en cherchant à trouver les parties droites des
règles dans la séquence de la proto-phrase courante pour les remplacer
par les parties gauches.
— Déterministes – non déterministes
Que l’analyseur soit descendant ou ascendant, le choix de la règle
à appliquer est parfois problématique. A un instant donné de l’ana-
lyse, il se peut qu’une proto-phrase puisse correspondre à plusieurs
dérivations qui ne vont pas toutes aboutir au résultat 2 . Un analyseur
déterministe applique seulement les dérivations qui conduisent à des
résultats. Deux alternatives permettent de construire des analyseurs
non déterministes. La première est peu heureuse : elle consiste à faire
machine arrière en cas d’échec pour explorer les autres dérivations
laissées en suspend quand plusieurs choix étaient possibles. Une autre
plus efficace, qu’on verra avec deux algorithmes (Earley et CKY), ap-
plique toutes les dérivations en parallèle au même instant. Certaines
vont aboutir, d’autres non. On peut dire que cette dernière méthode
est gourmande en place mais satisfaisante en durée du processus.
1. Une proto-phrase est une séquence de terminaux et de non terminaux qui dérive du
∗
terme initial. Soit x ∈ (Σ ∪ N )∗ /S ⇒ x
2. Si plusieurs dérivations gauches (resp. droites) peuvent aboutir à des résultats, la
grammaire est dite ambiguë.
12