0% ont trouvé ce document utile (0 vote)

6 vues24 pages

Introduction aux Langages Formels

Le document présente une introduction aux langages formels, leur définition, et les différents niveaux de langages associés à des machines abstraites. Il aborde également les automates d'états finis, leur fonctionnement, et les distinctions entre automates déterministes et non déterministes. Enfin, il traite des opérations sur les langages et des expressions rationnelles, ainsi que des théorèmes fondamentaux liés à ces concepts.

Transféré par

Mahamat Nour Mahamat Tahir

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

6 vues24 pages

Introduction aux Langages Formels

Transféré par

Mahamat Nour Mahamat Tahir

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

deux premières semaines ou ces deux notions

seront reprises rapidement.

0.2 Panoramique
Un langage formel est un ensemble de mots
le plus souvent infini. Les langages formels
furent initialement utilisés pour formaliser les
langues naturelles. Ils sont au cœur du traite-
ment automatique des langages de programma-
tions. C’est également la base de toute l’infor-
matique théorique. On distingue trois niveaux
de langage décrit dans la table 1. Chaque ni-
veau est associé à un type de machine abs-
traite capable de reconnaı̂tre les mots du lan-
gage. Pour les deux premiers niveaux, la ma-
chine abstraite est générée automatiquement,
nous verrons comment le faire. Le troisième ni-
veau est le cas général de ce qu’on peut calculer
avec un ordinateur (théorie de la calculabilité).
On considérera de plus un temps et un espace
mémoire raisonnable (théorie de la complexité)
Cours de Langages Formels .
2020
Frédéric Gruau
1 Langages formels
Definition 1 Un alphabet est un ensemble fini
noté Σ dont les éléments sont appelés lettres,
Introduction
un mot est une suite finie de lettres, notée u =
Le cours est fait au tableau, cela est plus 1 . . . un .
u
vivant, et plus interactif. Ce support ne com-
La longueur du mot u notée |u| est le nombre
prends pas les exemples nombreux développés
de lettres. On note Σ∗ l’ensemble des mots sur
en cours. Son utilité principale et de faciliter le
Σ, le mot de longueur nulle, appelé mot vide.
rattrapage en cas d’absence, et de permettre
aux étudiants de pas être obligé de tout le Definition 2 L’ensemble des mots est
temps prendre des notes. Il permet également muni d’une opération interne, le produit de
d’avoir une vue globale sur tout le contenu. concaténation, telle que si u = u . . . u et
1 n
Le cours est étroitement synchronisé avec les v = v . . . v , alors le produit u.v est le mot w
1 p
TDs, on peut le voir comme une préparation tel que w = u pour i ∈ [1..n] et w
i i n+j = vj
aux TDs. Il est également structuré par rapport pour j ∈ [1..p].
aux examens. Chaque cours fait l’objet d’un
TD, et d’un exercice, au partiel puis à l’exa- la concaténation des mots est associative et
men. Dans certain cas bien précis, une partie possède pour élément neutre. On note le pro-
du TD précéde le cours. duit sous la forme u.v
La puissance nieme d’un mot est définie par
0.1 Prérequis récurrence sur n comme suit : u0 = et un+1 =
[Link] . Muni du produit de concaténation et de
Les étudiants qui n’ont pas encore étudié son élément neutre, Σ∗ est un monoı̈de libre
les automates d’états finis ou les expressions sur Σ : tout mot u est soit le mot vide , soit
rationnelles, ont un retard important sur les commence par une certaine lettre a auquel cas
autres. Ce retard doit être comblé par un tra- il s’écrit de manière unique sous la forme a.v
vail supplémentaire très significatif durant les pour un certain mot v de taille diminuée de

1
Nom Description du langage phase de compilation machine abstraite
Langage régulier Expression rationnelles Analyse lexicale Automate d’état fini
Langage algèbrique Grammaires hors contexte Analyse syntaxique Automates à piles
Langage récursif Grammaire avec contexte. Typage Machine de turing

Table 1 – Les trois niveaux de langages principaux.

une unité. Il sera donc possible de prouver une Preuve. A∗ B est solution. le vérifier. Elle est
propriété P d’un ensemble de mots en montrant unique ? Soit L une solution, montrons que L =
P (), puis en montrant P (a.v) en supposant A∗ .B , comment ? par double inclusion !
P (v). 1- A∗ .B ⊂ L en substituant n − 1 fois L
par A.L + B dans le membre droit, on obtient
Definition 3 : Un langage est un ensemble de L = An L + An−1 B + An−2 B + ... + B On voit
mots apparaı̂tre A∗ .B, qui est donc inclus dans L.
2- L ⊂ A∗ B. Soit u dans L de longueur l
Le langage vide noté ∅ ne possède aucun mot. on choisit n = l + 1 dans l’équation précédente
Le langage unité {} est réduit au mot vide. L = Al+1 L+Al B+. . .+Al−1 B+Al−2 B+. . .+B.
On définit à nouveau des opérations sur les Si A ne contient pas epsilon, alors les mot de
langages, opérations ensemblistes classiques : Al+1 .L sont de longueur > l. Donc u n’est pas
L1 ∪ L2 désigne l’union des langages L1 et L2 , dans Al+1 .L. Donc il est dans le reste qui est
L1 ∩L2 désigne l’intersection des langages L1 et une partie de A∗ B.
L2 , Σ∗ \ L désigne le complémentaire dans Σ∗
du langage L. La concaténation peut s’étendre
au ensemble de mots : 2 Expressions rationnelles
— L1 .L2 = {u.v|u ∈ L1 et v ∈ L2 } désigne
le produit des langages L1 et L2 . Atten- On fait l’usage systématique de l’union, pro-
tion ce n’est pas le produit ensembliste. duit et étoile de Kleene. On considère les mots
{aa, a}.{ab, aab} = {aab, aaab, aaaab}. écrit sur Σ, completé des signes ’+’ (union aussi
n 0
— L tel que L = {} et L n+1 = [Link] noté |) ’.’ ’*’, ’(’,’)’
désigne la puissance nieme du langage L le langage Rat des expressions rationnelles
∗ i
— L = ∪i/i∈N L désigne l’itéré du langage sur l’alphabet Σ est définit par induction :
L. L’étoile de Kleene permet de passer a — une lettre de Σ est dans RAT
∗
l’infini (aa) = , aa, aaaa, aaaaaa, . . . = — est dans RAT
mot ayant un nombre pair de a = {u ∈ — Si e1 et e2 désignent des expressions ra-
a ∗ /|u|a mod 2 = 0}. tionnelles, alors
+
L = ∪i>0 Li désigne l’itéré strict du langage — e1 + e2 est dans RAT (somme)
L. On démontre l’égalité entre deux langages — e1 .e2 est dans RAT (produit)
de deux manières : — e∗1 est dans RAT (itérée de e1 )
1-Par des manipulation algébriques en utili- — (e) est dans RAT
sant les propriétés ensemblistes de l’union et Précédence : étoile>produit > somme.
de du produit, par exemple : l’associativité de Toute expression rationnelle dénote un lan-
l’union, (A ∪ B) ∪ C = A ∪ (B ∪ C), la distri- gage dit rationnel, définit aussi par induction :
butivité de l’union sur le produit (A ∪ B).C = — si u est une lettre ou Lang(u) = {u} ;
(A.C) ∪ (A.B) — Si e1 et e2 désignent des expressions ra-
2- Par la double inclusion. L1 = L2 ssi L1 ⊂ L2 tionnelles, alors
et L2 ⊂ L1 Exemple : démontrer la distributi- — Lang(e1 + e2 ) = Lang(e1 )∪Lang(e2 )
vité de l’union sur le produit. — Lang(e1 .e2 ) = Lang(e1 ) . Lang(e2 )
— Lang(e∗ ) = (Lang(e))∗ ).
Theoreme 1 Lemme d’arden : Si A et B sont — Lang((e)) = Lang(e).
deux langages, l’équation L = A.L ∪ B admet Abus de notation important : une expres-
A∗ B comme solution , de plus si A ne contient sion rationnelle est identifiée au langage qu’elle
pas , cette solution est unique. dénote.

2
Identités remarquables : Deux expres- Theoreme 2 Soit A = (Σ, Q, δ) un automate
sions rationnelles distinctes peuvent dénoter le fini déterministe complet. Alors, pour tout mot
même langage. Exemple : (a + b)∗ et (a∗ b∗ )∗ u ∈ Σ∗ et tout état q ∈ Q, il existe un unique
dénotent toutes deux le langage des mots état q 0 ∈ Q tel que q − u− > q 0
quelconques sur l’alphabet {a, b}.
On peut alors étendre l’application δ aux
1.r + s = s + r
mots, en posant δ(q, u) = q 0 ∈ Q tel que
2.(r + s) + t = r + (s + t)
q−u− > q 0 . Un automate qui n’est pas complet,
3.(rs)t = r(st)
le devient si on ajoute un nouvel état appelé
4.r(s + t) = rs + rt
poubelle vers lequel vont toutes les transitions
5.(r + s)t = rt + st
manquantes. Exercice : Compléter l’automate
6.∅∗ =
précédent. C’est pas forcément une bonne idée
7.(r∗ )∗ = r∗
de rajouter une poubelle.
8.(r∗ s∗ )∗ = (r + s)∗
Definition 6 Un automate déterministe vient
avec la donnée d’un état initial q0 ∈ Q et d’un
ensemble d’états finaux F ⊆ Q ;
3 Automates d’états finis.
Un mot w est reconnu par l’automate s’il existe
C’est un formalisme très général qui peut un calcul dit réussi issu de l’état initial q0 et ter-
modéliser des dispositifs automatiques, des minant dans un état final après avoir lu le mot
systèmes réactifs, des objets mathématiques ou w. On note Lang(A) le langage des mots re-
physique, des circuit digitaux. . . connus par l’automate A. Un langage reconnu
par un automate est dit reconnaissable. On ap-
3.1 Automates déterministes pelle REC l’ensemble des langages reconnais-
sables. Il est clair que l’ajout d’une poubelle
Definition 4 Un automate fini déterministe
ne change pas les mots reconnus. Si l’automate
A est un triplet (Σ, Q, δ) où
A est complet, on peut reformuler la condition
1. Σ est le vocabulaire de l’automate ;
d’acceptation des mots comme u ∈ Lang(A) ssi
2. Q est l’ensemble fini des états de l’automate
δ(q0 , u) ∈ F .
3. δ : Q × Σ → Q, est une application partielle
appellée fonction de transition de l’automate.
3.2 Automates non déterministes
Si δ(q, a) = q 0 , on peut noter cela q − a → q 0 . Definition 7 Un automate non-déterministe
Exercice : Donner l’automate a trois états qui A est un triplet (Σ, Q, δ) où
reconnait les entier en binaire. q0 − 1− > q1 − 1. Σ est l’alphabet de l’automate
0, 1− > q1 ; q0 − 0− > q2 ; q1 , q2 finaux 2. Q est l’ensemble des états de l’automate
3. δ : Q × Σ → P (Q) la fonction de transition.
Definition 5 Etant donné un automate
déterministe A = (Σ, Q, δ), et un mot Exemple : L’Automate des mots qui
u = u0 , u1 , ...un on appelle calcul as- contiennent ”aa” : q0 − a, b− > q0 − >
socié au mot une suite de transitions a− > q1 − a− > q2 − a, b− > q2 ; q2 final.
q0 − u1 − > q1 − > ... − un − > qn . on On notera comme précédemment q − α →
écrit q0 − u− > qn q pour q ∈ δ(q, α) avec α ∈ Σ. δ(q, u)
est l’ensemble (peut-être vide) des états attei-
Le calcul produit par la lecture d’un mot gnables depuis q en lisant le mot u. Automate
u par un automate fini déterministe est au- déterministe= cas particulier d’automate non-
tomatique : la lecture des lettres composant déterministe. La notion de calcul est la même
le mot provoque des transitions bien définies non-déterministe / déterministe. Il peut y avoir
jusqu’à être bloqué en cas de transitions man- plusieurs calculs issus de l’état initial q0 , qui
quantes, ou bien jusqu’à atteindre un certain lisent un mot w donné, dont certains peuvent
état après la lecture complète du mot. Lorsque se bloquer et d’autres pas, si un calcul échoue,
δ est totale, l’automate est dit complet. On cela veut rien dire, il faut tout explorer. Recon-
en déduit la propriété fondamentale des auto- naissance = au moins un calcul démarrant sur
mates déterministes complets : l’etat initial, arrive sur un final.

3
Déterminisation. Si Q est l’ensemble des On notera q − α → q 0 pour q 0 ∈ δ(q, α), avec
états d’un automate non-déterministe, l’en- α ∈ Σ ou α = .
semble des états de l’automate déterministe as- Exercice : construire un automate non-
socié sera P (Q), l’ensemble des parties de Q. il déterministe avec transitions vides reconnais-
y en a exponentiellement plus. sant le langage sur l’alphabet {0, 1} contenant
au moins une occurrence du mot ”00”, ou une
Definition 8 Soit A = (Σ, Q, δ, q0 , F ) occurrence du mot ”11.
un automate non-déterministe. On définit q0 − 0, 1− > q0 − − > q1 , q2 .
Det(A) comme l’automate (Σ, P (Q), δdet ) q1 − 0− > q30 − 0− > q3 − − > q5
où δdet (K, a) = ∪q∈K δ(q, a).. L’état q2 − 1− > q40 − 1− > q4 − − > q5
initial est {q0 }. Les etats finaux sont q5 − 0, 1− > q5
{K ∈ P (Q)|K ∩ F 6= ∅} Morale : avec des epsilon-transitions, on
construit un automate qui reconnaı̂t la réunion
Theoreme 3 Soit A un automate non-
de deux langages, à partir des deux automates
déterministe. Alors Det(A) et déterministe et
qui reconnaissent chacun des langages. Cette
reconnaı̂t le même langage que A.
technique sera utilisée pour la démonstration
Exercice Déterminiser l’automate qui redu théoreme de Kleene ;
connaı̂t les mot contenant aa. Faire trois Note : Les calculs d’un automate avec transi-
colonnes contenant des ensembles d’états : tions vides autorisent le passage par un nombre
colonne de gauche : les ensembles visités, quelconque de transitions vides au cours de
colonne du milieu : transitions par 0, l’exécution. Le nombre d’états parcourus peut
colonne de droite : transition par 1. être bien supérieur au nombre de lettres lues.
Après, on peut renuméroter les états,
éventuellement. Principe de la preuve de Élimination des transitions vides. Nous
déterminisation : Les états sont étiquetés par voulons maintenant montrer que le langage re-
l’ensemble des noms des états de l’automate connu par un automate avec transitions vides
non-déterministe qui le constituent. S’il est peut également l’être par un automate non-
possible dans l’automate non-déterministe déterministe sans transitions vides. Il faut ajou-
d’atteindre les états q1 , . . . , qn depuis l’état
ter de nouvelles transitions dans l’automate :
q en lisant la lettre a, alors, dans l’automate 1- Pour chaque chemin d’un état s à un état
déterminisé, depuis tout état contenant l’état t formé de epsilon-transitions, et pour chaque
q, en lisant cette même lettre a, on atteindra transition de t à un état u portant une lettre a,
un état contenant q1 , . . . , qn ajouter une transition de s à u d’étiquette a ;
Les automates déterministes, et non 2- Pour chaque chemin d’un état s à un état t
déterministes reconnaissent les même lan- terminal formé de epsilon-transitions, ajouter s
gages. les automates déterministes sont parfois à l’ensemble des états terminaux ;
exponentiellement plus gros, la borne étant Notons que cette construction n’augmente pas
atteinte, c’est montré dans le TD. le nombre d’états.
Exercice enlever les epsilon transitions de
3.3 Automates avec transitions vides l’automate précédent. Attention, y a des tran-
sition de q0 vers q30 et q40 lorqu’on dés-epsilonne.
C’est une autre façon d’exprimer le non-
déterminisme, ces automates sont aussi appelés
asynchrone. Les transitions étiquetées par , 4 Theoreme de kleene.
dénotent l’absence de lettres lue lors de la tran-
sition. Theoreme 4 RAT=REC

Definition 9 Un automate non-déterministe Preuve : on utilise la double inclusion

A avec transitions vides est un triplet (Σ, Q, δ)
où 1. Σ est l’alphabet de l’automate 1-RAT ⊂ REC.
2. Q est l’ensemble des états de l’automate Si E est une expression rationnelle, il existe
3. δ : Q × (Σ ∪ ) → P (Q) est la fonction de un automate qui reconnait le langage associé,
transition de l’automate. demo par induction :

4
1-Cas de base 5 Minimisation d’un auto-
Si e=vide pas d’état mate déterministe
si e = un etat initial acceptant
si e = une lettre, deux états 5.1 Exemple fil conducteur
2-Induction
Faut montrer que si A reconnaı̂t L1 et A0 re- Soit le langage L = (a+b)∗aba(a+b)∗. L’au-
connaı̂t L2 on peut construire un automate re- tomate reconnaissant ce langage est q0 − b− >
connaissant : L1 + L2 , L1 .L2 , L∗1 faire des des- q0 − a− > q1 − a− > q1 − b− > q2 − a− >
sins. q3 − a, b− > q3 et la transition q2 − b− > q1.
Si e = e1 + e2 on rajoute un état initial et un Cet automate est minimal, on rajoute des états
final et on recolle avec des epsilon, initial sur pour le rendre non minimal : on détriple q1 en
initiaux, finaux vers final (comme dans l’ exo rajoutant q1 − a− > q10 − a− > q”1 et on
traité) dédouble q0 , q2 , q3 , en donnant le même sens
si e = e1 .e2 suffit de rajouter un epsilon des aux état de même indice : les états 0,1,2,3
finaux du premier vers l’initial du second. attendent respectivement aba,ba,a,epsilon. Les
si e = e∗1 on rajoute des epsilon de final vers états q1 , q10 , q”1 ont tous même ”futur”, ils at-
initial, en laissant les meme finaux ca recon- tendent les même mots et devront donc être
nait L+ 1 apres faut rajouter epsilon en ajoutant
fusionné.
un autre état initial et aussi final.
Definition 10 Le futur d’un état est l’en-
semble des mots qui méne de cet états à un
final
2-REC ⊂ RAT. On calcule directement l’ex- Le futur de q0 est le langage reconnu. Les futurs
pression rationnelle du langage reconnu par un ont déjà été utilisé pour poser un système de n
automate. il s’obtient par la résolution d’un en- équations a n inconnues permettant de calcu-
semble d’équations à n inconnues, ou n est le ler le langage reconnu par un automate donné,
nombre d’états. A chaque état qi , i = 0..n − 1, avec Arden.
on associe un langage Li appellé futur de qi , Pour notre automate : dire les futurs :
qui contient les mot menant de qi vers un état futur0= L,
final. On a le système de n équations à n in- futur1=ba(a+b)* + L
connues suivant : Li = Y1 + Xi,0 .L0 + Xi,1 .L1 + futur2=a (a+b)* + L,
... + Xi,n−1 .Ln−1 ou Yi = si qi est dans F et futur3=(a+b)*
Xi,j = l’ensemble des lettres étiquetant les tran-
sition de qi vers qj . Ce système se résout avec
le Lemme d’Arden, et par substitution. Cela
donne n expressions rationnelles pour chacun 5.2 Minimisation d’automate.
des Li et en particulier pour L0 qui est le lan- Idée clef : les états ayant même futur peuvent
gage reconnu par l’automate. être fusionnés.
On va donc calculer une partition des états
regroupant dans un même sous ensemble les
états ayant même futur. On calcule progressive-
Exemple : Soit L le langage des mot sur a, b ment cette partition en considérant ”ont même
contenant un nombre pair de a. L’automate est futur” avec seulement les mots de longueur k.
simple : Deux états q0 et q1 , transition par b de On augmente progressivement k en partant de
q0 vers q0 et de q1 vers q1 , transition par a de q0 zéro. Pour k = 0, p0 sépare les finaux des non-
vers q1 et vice-versa. q0 à la fois initial et final. finaux. Pour passer de pk à pk+1 , avoir même
L0 = + b.L0 + a.L1 futur à k + 1 lettre c’est lire une lettre et tom-
L1 = b.L1 + a.L0 ber dans le même sous ensemble d’états qui on
L1 = b∗ a.L0 (arden) même futur de k lettres ; On considére une à
on remplace L0 = + b.L0 + a(b∗ .a.L0 ) une chaque lettre a de l’alphabet, et chaque
on identifie pour appliquer arden, une autre classe C de pk , et on scinde en deux C si l’image
fois, on trouve L0 = (ab∗ a + b)∗ des éléments de C par δ arrive dans des classes

5
différentes de pk . On scinde en regroupant les d’équivalence de ∼L . Donc, il y a une corres-
états de C qui ont la même image ; pondance bi-univoque entre les classe de ∼L et
Sur l’exemple, on sépare d’abord q3 , q 0 3, puis les états du minimisé.
q2 , q 0 2 etc. Au bout d’un moment l’algorithme Donc, pour obtenir directement les états
converge, car on ne peut pas éternellement du minimisé à partir du langage, on prends
scinder. A ce moment la, on peut fusionner états= classes d’équivalence de ∼L (mots qui
ensemble les états de chaque sous-ensemble ont même futur).
de la partition. Cela va donner un automate
i.e. l’image par δ sera cohérente. Montrez sur
l’exemple, que si on fusionne avant conver-
gence, l’image par δ n’est pas cohérente, on 5.4 Existence et unicité d’un auto-
n’obtient pas un automate.
mate minimal

5.3 Calcul direct de l’automate mi- Theoreme 5 (Myhill-Nerode) Si L est ration-

nimal. nel, alors ∼L à un nombre fini de classe, soit
La notion de futur, peut se définir sur des AL l’automate défini par
états, mais aussi directement sur des mots : 1- les états sont les classes de ∼L , on note [u]
la classe de u.
Definition 11 Soit L un langage, w un mot. 2- L’état initial est []
futurL (w) = {u/wu ∈ L} 3- δ([u], a)= [ua] est bien définie
4- Les états finaux sont ceux dont le futur
Pour tout automate qui reconnaı̂t le langage : contient .
Le futur d’un mot, et le futur de l’état vers le- AL reconnait L avec le moins d’états possible.
quel ce mot mène. Le futur d’un état et le futur
de n’importe quel mot qui y mène. Lexique : on
appelle aussi cela ”résidu”.
Preuve simplifiée :
Definition 12 u ∼L v iff u, v ont même futur Step1 δ est bien défini, il faut montrer que
dans L la transition ne dépends pas du représentant
choisi dans la classe de u car ∼L est une
Property 1 ∼L est une relation congruence droite : si u ∼L v alors ua ∼L va
d’équivalence. pour toute lettre a. Cela vient du fait que si
deux mot on même futur en rajoutant un suf-
Rappel de ce qu’est une relation fixe ca reste vrai.
d’équivalences. Step2 Prouvons que AL est minimal. Soit
ex1 : x ∼ y si x et y on meme plafond A un autre automate qui reconnnait L et la
(nombre entier au dessus), quelles sont les relation∼A définie par u ∼A v si u, v ménent
classes ? vers le même état de A. Idée clef : si deux mots
ex2 : x ∼ y si x = y modulo 2, puis modulo 4. ménent vers le même état de A, alors ils ont
Quelles sont les classes ? forcément même futur. Cela s’écrit u ∼A v ⇒
donner les 4 classes d’équivalence pour ∼L u ∼L v. Cela corresponds a la définition de être
(a+b)*bb \ L ; futur= L , plus fin : ∼A est plus fine que ∼L ; Reparler de
(a+b)*a \ L ; futur=ba(a+b)* +L l’exemple de la relation ”est egal modulo 4”,
(a+b)*ab \ L ; futur=a (a+b)* +L qui est plus fine que ”est egal modulo 2”. Cela
L ; futur=(a+b)* implique que les classe de ”est égal modulo 2”
s’obtiennent en fusionnant les classes de ”est
Remarque : Les états d’un automate égal modulo 4”. De même, ∼A est plus fine que
déterministe partitionnent les mots, car un mot ∼L implique que les états de AL s’obtiennent
ne peut mener que vers un seul état. Idée clef : en fusionnant des états de A. Comme A a été
Dans le minimisé, tout les mots qui ont même pris quelconque, cela montre bien que AL à
futur devrait mener vers le même état ; ”Tout moins d’états qu’un automate quelconque, et
les mots qui ont même futur” c’est une classe il est donc minimal en nombre d’états.

6
6 Propriétés de clôture des sont obtenus par pompage de v dans m.
langages reconnaissables Preuve : C’est le même argument que ce-
lui que l’on vient de développer pour mon-
Soit f une opération d’arité n sur les mots, trer que le langage {an bn |n ∈ N } n’est pas
et L1 , ...Ln des langages. On définit le langage reconnaissable. On se donne un automate A
f (L1 , . . . , Ln ) = f (u1 , . . . , un )/ui ∈ Li complet, sans transition vide reconnaissant le
On dit que les langages reconnaissables sont langage L, et on note N = |Q| qui est po-
clos par une opération f si f (L1 , . . . , Ln ) est sitif strictement puisque A est complet. Soit
reconnaissable lorsque les langages L1 , . . . , Ln maintenant m ∈ L de taille au moins N , et
le sont. c = q0 → q|m| ∈ F un calcul reconnaissant m.
Les langages reconnaissables possèdent de Comme l’automate n’a que N ≤ |m| états, il
très nombreuses propriétés de clôture, en par- existe deux entiers i et j tels que 0 ≤ i < j ≤ N
ticulier par les opérations ensemblistes simple : et qi = qj . Il existe donc trois mots u, v, w tels
union, intersection, complémentaire. Par sub- que : c = q0 −u → qi −v → qj −w → q|m| ∈ F et
stitution (de lettres par des mots = homo- l’on vérifie immédiatement les conditions m =
morphisme), par homomorphisme inverse, par uvw, v 6= , |uv| ≤ N . De plus, comme qi = qj ,
pompage, etc. le calcul i = q0 −u → qi −v k → qj − → q|m| ∈ F
Les clôtures ont deux utilités : reconnait le mot uv k w qui est donc un mot de
1- montrer que certains langages sont bien re- L.
connaissables,
2- montrer que certains langages ne sont
Contraposée du lemme de la pompe.
pas reconnaissables, (contraposée pompe, ou
Être pompable est une condition nécessaire,
démonstration par l’absurde)
mais pas suffisante. Il existe des langages non
reconnaissables qui satisfont le “Lemme de la
7 Pompage des langages re- pompe”. On ne peut donc pas déduire d’un lan-
connaissables gage qu’il est reconnaissable en montrant qu’il
satisfait le “Lemme de la pompe”. Mais l’on
Le langage L = {a b , n ∈ N } n’est pas re- peut s’en servir pour montrer qu’un langage
n n

connaissable. Par l’absurde, si il l’était, soit un n’est pas reconnaissable, puisque, par contra-
automate A = (Σ, Q, δ, q0 , F ) qui le reconnait. position, un langage qui ne satisfait pas le
Considérons l’application φ : n 7→ δ(q0, an ). “Lemme de la pompe” ne peut pas être recon-
φ ne peut être injective, car son ensembe de naissable.
départ est infini, et son ensemble d’arrivée est Exprimons donc la négation de la propriété
fini. Donc il existerai n, m tel que φ(n) = de la pompe, cela se fait par application des
n n m n
φ(m) = q. mais alors δ(q0 , a b ) = δ(q0 , a b ) règles usuelles de logique permettant de pous-
absurde, l’un appartient a F , l’autre pas. ser les négations à l’intérieur des formules en
Plus généralement, si un automate avec états changeant les quantificateurs,
dans Q, est complet sans transitions vide, tout ¬ Pompe =
calcul de plus de n = |Q| états, passe deux fois ∀N > 0,
par le même état durant les n premières tran- ∃m ∈ L, |m| ≥ N tel que
sitions. Ce cycle peut etre supprimé, ou itéré. ∀u, v, w ∈ Σ∗ telque m = uvw, v 6= , |uv| < N,
Faire un dessin. ∃k ∈ N tel que uv k w ∈ / L.

Theoreme 6 Tout langage L reconnaissable

satisfait la propriété Pompe : 8 Nettoyage des automates
∃N > 0 tel que
∀m ∈ L, tel que |m| ≥ N On peut passer d’un automate non-
∗
∃u, v, w ∈ Σ tq m = uvw, v 6= , |uv| ≤ N déterministe avec transitions vides vers un
k
∀k ∈ N, uv w ∈ L automate non-déterministe sans transitions
vides en temps linéaire en la taille, sans rajou-
Soit m = uvw un mot sur le langage Σ . On ter d’états ⇒ la complexité des transformations
dit que les mots de la forme uv k w pour k ∈ N est inchangée.

7
Qu’il soit ou non déterministe, un automate Décision du plein Si l’automate est
peut posséder des états retirables sans changer déterministe, ce problème a la même com-
le langage reconnu. plexité que le problème du vide, puisqu’ils
s’échangent par permutation des états accep-
Definition 13 Étant donné un automate tants et non-acceptants. Cela n’est pas vrai
(déterministe ou pas, avec ou sans transitions des automates non-déterministes.
vides) A = (Σ, Q, q0 , F, δ), l’état q ∈ Q est
accessible, s’il existe w tel que q0 − w → q ; Theoreme 9 Le plein du langage reconnu
productif, s’il existe w tel que q − w → f ∈ F ; par un automate déterministe (resp. non-
utile, s’il est à la fois accessible et productif. déterministe) est décidable en temps linéaire
(resp. exponentiel).

Un automate est dit réduit si tous ses états

Le cas des automates déterministes : le
sont utiles. Nettoyer = enlever les état inutiles.
passage au complémentaire se fait en temps
Un état q est productif ssi q ∈ F ou bien linéaire sans changer la taille de l’automate
il existe un état productif q 0 et une lettre (à un facteur près). Pour les automates non-
a ∈ (Σ ∪ ) tels que q 0 ∈ δ(q, a). ⇒ algo- déterministes, il est nécessaire de déterminiser
rithme simple en temps linéaire, ajouts succes- au préalable, d’où le saut de complexité.
sifs d’états productifs à un ensemble réduit ini-
tialement à F .
Un état q est accessible ssi q = q0 ou bien
10 Grammaire hors contexte.
il existe un état accessible q 0 et une lettre
a ∈ (Σ ∪ ) tels que q ∈ δ(q 0 , a). algorithme — Décrit des langages
similaire, temps linéaire, par ajouts successifs — Inspirés des grammaires de langage na-
d’états accessibles à un ensemble réduit initia- turel, exemple : Phrase → sujet verbe
lement à q0 . complément.
— Différence : une grammaire peut générer
Theoreme 7 Pour tout automate fini A, des mots arbitrairement long, les phrases
déterministe ou pas, il existe un automate fini restent de longueur raisonnable.
de même nature sans états inutile qui peut être
obtenu à partir du premier en temps linéaire.
Definition 14 Une grammaire G hors
contexte est un quadruplet (ΣN ,ΣT , S, R) où
9 Décision et temps lineaire. 1. ΣT = alphabet de symboles dits terminaux ;

Nettoyer sert a montrer que certain 2. ΣN alphabet de symboles non-terminaux ;

problèmes sont décidables et de plus rapide- 3. Σ = ΣN ∪ ΣT = alphabet total de G ;
ment. Être décidable signifie que il existe un
programme qui réponds oui ou non, au bout 4. S est un non-terminal appelé axiome ;
d’un temps fini. Rapide signifie ici en temps 5. R ⊆ P(ΣN × Σ? ) est un ensemble fini de
linéaire, proportionnel à la taille du problème règles notées g → d si (g, d) ∈ R.
Un problème deux fois plus gros prends un
temps deux fois plus gros.
Notation : On utilisera des majuscules pour
les non-terminaux, et des minuscules pour les
Décision du vide Le langage reconnu est terminaux.
vide ssi l’automate nettoyé n’a plus d’état or- Exemple1 La grammaire S → aSBC, CB →
mis l’état initial. BC, aB → ab, bB → bb, bC → bc, cC →
cc. Elles est hors-contexte, car les membres
Theoreme 8 Le vide du langage reconnu par gauches contiennent plusieurs lettres. Faire une
un automate quelconque est décidable en temps dérivation, montrer que cela génère an bn cn , n >
linéaire. 0.

8
10.1 Langage engendré. Id|Cte|E + E|E ∗ E|(E) . En vrai, Cte et Id
représente des constantes ou des identifica-
On engendre les mots du langage, en
teurs. Pour l’analyse syntaxique, on considère
récrivant un mot u ∈ Σ? en un nouveau mot v ∈
toutes les constantes (resp. tout les identifica-
Σ? . On remplace une occurrence (quelconque)
teurs) comme le même terminal. Faire deux
d’un membre gauche de règle présent dans u
dérivation toutes les deux droites de x + 4 ∗ y
par le membre droit de cette règle.
distinctes, montrer que le sens diffère ;
Definition 15 Étant donnée une grammaire
Si la grammaire est hors-contexte on peut
G = (ΣT , ΣN , S, R), on dit que le mot u ∈ Σ?
représenter une dérivation par un arbre :
se récrit en le mot v ∈ Σ? dans G avec la règle
g → d, et on note u − g, d → v si u = w1 gw2 , Definition 17 Étant donnée une grammaire
et v = w1 dw2 ; G = (ΣT , ΣN , S, R), les arbres de dérivation
de G sont des arbres avec la racine (resp. les
Plus généralement, on dit que le mot v ∈ Σ?
nœuds internes, les feuilles) étiqueté(es) par
dérive du mot u ∈ Σ? , dans la grammaire G,
l’axiome, (resp. des non terminaux, des termi-
et on note u →∗ v, (fermeture transitive de
naux) vérifiant de plus que si les fils pris de
→) s’il existe une suite finie w0 , w1, . . . , wn de
gauche à droite d’un nœud interne étiqueté par
mots de Σ? telle que w0 = u, wi → wi+1 pour
le non- terminal N sont étiquetés par les sym-
tout i ∈ 0, . . . N − 1, et wn = v. On peut indi-
boles respectifs α1 , ..., αn , alors N → α1 . . . αn
quer le non-terminal récrit en le soulignant. La
est une règle de la grammaire G.
réécriture est itéré à partir de l’axiome jusqu’à
l’élimination complète des non-terminaux. Un arbre de dérivation résume plusieurs
dérivations possibles, réalisées avec un ordon-
Definition 16 , Le langage engendré par la nancement différent.
grammaire G est l’ensemble des mots de Σ?T
qui dérivent de l’axiome de G, que l’on note
10.3 Ambiguı̈té
par Lang(G).
Deux arbres différents, cela implique un non-
Classification de Chomsky des gram- déterminisme, et aussi deux calculs différent.
maires : On n’aime pas, on va définir l’ambiguı̈té comme
— type 0 : membre gauche arbitraire suit, et chercher ensuite a l’éviter.
membre droit arbitraire (Machine de Tu-
ring) Definition 18 Une grammaire G est am-
— type 1 : on passe biguë s’il existe un mot w ∈ Lang(G) qui
— type 2, hors contexte : membre gauche = possède plusieurs arbres de dérivation s dans
un seul non terminal (Automate a Pile) G.
— Type 3, régulier : membre droit contient
un seul non terminal toujours tout a la Comment enlever l’ambiguité ? (Exo de
fin (Automate d’etat fini) TD)
Exemple2 (Grammaires hors-contexte) La Méthode 1, bricolage, on introduit d’autre
grammaire S → |aSb génére le langage non terminaux pour forcer un ordre : E →
{an bn |n ≥ 0}. E + F |F
Exemple3 (grammaire réguliére) : La gram- F → F − G|G
maire N → 0|1M, M → 0M |1M | génére les G → id|cte|(E)
entiers naturels en représentation binaire, sans Méthode 2, la méthode utilisée en pratique, car
zéros redondants : par exemple, 01 n’est pas plus simple, et plus élégante. On utilise des
dedans. méta régles, extérieures à la grammaire :
— priorité de * sur +
10.2 Arbre de dérivation — associativité à gauche de +, −, =, /.

Considérons la grammaire suivante : Definition 19 Réécriture droite (resp gauche)

ΣT = {+, ∗, (, ), Id, Cte}, ΣN = {E}, E → on réécrit le plus a droite (resp. gauche)

9
La réécriture droite (resp. gauche) corres- Fin Faire
ponds a un parcours droit (resp. gauche) Fin Faire ;
de l’arbre de dérivation. On parle aussi de Enlever toutes les règles M → N
dérivation droite et dérivation gauche. Il
y a une correspondance bi-univoque entre 4. Suppression des non terminaux non pro-
dérivation gauche (resp. droite) et arbre deductifs : Calculer les non terminaux productifs ;
dérivation. Enlever tous les autres
Propriété : une grammaire G est non am- 5. Suppression des non terminaux non at-
bigüe si et seulement si tout mot a une seule
teignables : Calculer les non terminaux attei-
dérivation droite (resp. gauche). gnables ; Enlever tous les autres
On remarque que chaque étape ne remet pas
10.4 Nettoyage de grammaire. en cause la précédente, et donc la grammaire
obtenue est propre. Ce ne serait pas le cas si
Definition 20 Une grammaire hors-contexte
l’on inversait les deux dernières étapes, comme
G = (ΣT , ΣN , S, R) est dite propre si elle
le montre l’exemple S → aM N, M → a.
vérifie :
1. ∀N → u ∈ R, u 6= ou N = S
10.5 Decidabilité
2. ∀N → u ∈ R, On n’a pas de S dans u
3. Les non-terminaux sont tous utiles, c’est- — Lang(G) = vide ? on nettoie on regarde
à-dire à la fois atteignable et productif. si il reste qqc
— Lang(G) infini ? on nettoie et on regarde
4. Il n’y a pas de règles ou on remplace un si il y a un cycle (un non-terminal X tel
non terminal par un autre. que X → αXβ)
— un mot u est il dans Lang(G) ? on met
Un non-terminal est dit atteignable si on peut
sous FNC et on utilise l’algo CYK vu en
le générer depuis l’axiome, il est dit produc-
PIL.
tif s’il peut générer une chaı̂ne de terminaux ;
— G est elle ambigüe ? indécidable, on fera
Donner des exemples négatifs pour illustrer ;
la démo en TD, mais oui.
Theoreme 10 Pour toute grammaire hors-
contexte G = (ΣT , ΣN , S, R), il existe 11 Analyse lexicale
une grammaire hors-contexte G’ propre qui en-
gendre le même langage. Lesétudiantsonttoustrèsbon
l’analyse lexicale decoupage le texte source
Preuve : La mise sous forme propre d’une
en mots appeles des tokens :
grammaire hors-contexte est la succession de
Les étudiant sont tous très bon
5 étapes qui terminent.
De même que dans les langues naturelles, ce
1. On rajoute une règle S 0 → S, S 0 devenant
découpage en mots facilite le travail de la phase
le nouvel axiome ;
suivante, l’analyse syntaxique.
2. Élimination des M → . Calculer l’en-
semble E = {M ∈ ΣN |M →∗ };
Pour tout M ∈ E Faire Role des séparateurs. Le texte source est
Pour toute règle N → αM β Faire une suite de caractères. les blancs (espace, re-
Ajouter la règle N → αβ tour chariot, tabulation, etc.) permettent de
Fin Faire ; séparer deux tokens
Fin Faire Exemple : pour le source camel : fun x →
Enlever les règles M → si M 6= S 0 x + 1 ou sont les frontières ?
funx = un seul token (l’identificateur funx)
3. Élimination des règles M → N . et fun x =deux tokens (le mot clef fun et l’iden-
Calculer les paires (M, N ) telles que M →∗ N tificateur x)
Pour chaque paire (M, N ) calculée Faire Les blanc ne sont pas toujours nécessaire
Pour chaque règle N → u Faire (entre x, + et 1 par exemple). Les blancs n’ap-
Ajouter la règle M → u paraissent pas dans le flot de tokens renvoyé.

10
Les commentaires jouent le role de blancs et par celle des identificateurs
sont aussi virés. ⇒ on classe les tokens par ordre de priorité.

11.1 Notion de Token. L’algorithme qui gère le gros automate

unique. L’analyseur lexical mémorise le der-
Un token comprends un numéro de classe nier état final rencontré. Lorsqu’il n’y a plus de
qui corresponds à un terminal de la grammaire transition possible, de deux choses l’une :
spécifiant la syntaxe du programme. Un token a
aussi une valeur. Certaines classes de token ont 1. Aucun état final memorisé ⇒ echec.
une seule valeur possible : mot clef, opérateur 2. On a lu le préfixe w de l’entree wv, avec
binaire . . .. D’autres classes en ont plusieurs, w la chaı̂ne reconnue par le dernier état
dans ce cas la valeur est calculée a partir de la final rencontré. ⇒ on renvoie le token w,
sous chaı̂ne associée au token. Exemple : pour et l’analyse redémarre sur v concaténé au
la classe cte, la valeur est l’entier calculé a par- reste de l’entrée.
tir de la séquence de chiffres représentant la
constante. Pour la chaine ”32” il faut traiter L’algorithme des fois, ne marche pas
les caractères ’3’ et ’2’, et calculer 3 ∗ 10 + 2. alors que il pourrait. Avec les trois expres-
sion a, ab, bc, l’analyse lexicale échoue sur abc
Comment spécifier classes de token. (ab est reconnu, comme plus long, puis echec
Pour chaque classe : sur c) pourtant le mot abc appartient au lan-
— On donne une expressions rationnelle gage (a|ab|bc)∗
— L’analyseur génère l’ automate associé.
Exemples : 11.2 Analyse lexicale avec Ocamllex
le mot clef ”fun”0 − f − > 1 − u− > 2 − n− > 3 (pour le TP)
final
constante entière 0 -chiffre − >1-chiffre − > 1 un fichier ocamllex porte le suffixe .mll et a
final la forme suivante
identificateur 0-lettre− >1 -lettre+chiffer − > {
1 final. % ocamllex [Link]
... code OCaml arbitraire ...
Le gros automate unique. L’ analyseur }
lexical construit un automate d’états fini qui rule f1 = parse
fait la reunion de tous ces petits automates. | regexp1 { action1 }
| regexp2 { action2 }
Fonction de l’analyseur | ...
— Décomposer un mot (le source) en une and f2 = parse
suite de mots reconnus. ambiguité pos- ...
sible. and fn = parse
— Construire les tokens : les états finaux ...
contiennent des actions, pour calculer les {... code OCaml arbitraire ...}
valeurs des tokens. La compilation de ce fichier produit un fichier
OCaml [Link] qui définit une fonction pour
Résolution de deux types d’ambiguités. chaque analyseur, f1 , . . . , fn :
Ambiguı̈té 1 : le mot funx est reconnu par val f 1 : [Link] → τ1
l’expression régulière des identificateurs, mais val f 2 : [Link] → τ2
contient un préfixe reconnu par une autre ex- ...
pression régulière (fun) val fn : [Link] → τn
⇒ on fait le choix de reconnaı̂tre le token le le type [Link] est celui de la structure de
plus long possible donnees qui contient l’etat d’un analyseur lexi-
Ambiguı̈té 2 : le mot fun est reconnu par l’ex- cal. la fonction from channel permet de conns-
pression régulière du mot clef ”fun” mais aussi truire un lexbuf a partir d’un fichier ouvert :

11
val from channel : rule token = parse
[Link] channel → lexbuf | "(*" { comment lexbuf }
| ...
‘
Opérateur pour décrire des expression
and comment = parse
réguliére lex :
| "*)" { token lexbuf }
_ n’importe quel caractere | _ { comment lexbuf }
’a’ le caractére ’a’ | eof{failwith
"foobar" la cha^ ıne "foobar" "comment non terminé"}
[ caracteres ] ensemble de caracteres
(par ex. [ ’a’-’z’ ’A’-’Z’]) | ...
[^caracteres] complementaire
(par ex. [^ ’"’])
r1 | r2 alternative Avantage : on traite correctement l’erreur
r1 r2 concatenation liée a un commentaire non fermé. Autre
r* etoile intérêt : on traite facilement les commentaires
r+ une ou plusieurs occurence =rr* imbriqués. 1- Avec un compteur.
r? une ou zero occurence =epsilon | r
eof la fin de l’entree rule token = parse
| "(*" { level := 1;
comment lexbuf;
On peut nommer des expressions regulières : token lexbuf }
| ...
let letter = [’a’-’z’ ’A’-’Z’] and comment = parse
digit = [’0’-’9’] | "*)" { decr level;
if !level > 0 then
rule token = parse comment lexbuf }
| letter (letter | digit | ’_’)* | "(*" { incr level;
as s{ Tident s } comment lexbuf }
| digit+ as s{Tconst int_of_string s} | _ c{ comment lexbuf }
| eof {failwith
On se donne un type Caml pour les tokens
"comment non terminé" }
type token =
2- Voire même, sans compteur, en utilisant
| Tident of string
la pile des appels :
| Tconst of int
| Tfun
rule token = parse
on peut récupérer la chaı̂ne reconnue, | "(*" {comment lexbuf;
ou les sous-chaı̂nes reconnues par des sous- token lexbuf}
expressions régulières, a l’aide de la construc- | ...
tion caml ”as”. Dans une action, il est possible and comment = parse
de rappeler récursivement l’analyseur. Le tam- | "*)" { () }
pon d’analyse lexicale doit être passé en argu- | "(*" { comment lexbuf;
ment ; il est contenu dans la variable lexbuf. Il comment lexbuf }
est ainsi facile de traiter les blancs : | _ { comment lexbuf }
| eof {failwith
rule token = parse "comment non terminé"}
| [’ ’ ’\t’ ’\n’]+ { token lexbuf }
Note : Le langage des commentaires im-
Pour traiter les commentaires, on peut utili- briqués n’est pas rationnel. Le fait d’utiliser des
ser une expression régulière ... ou un analyseur actions permet donc de dépasser la puissance
dédié : des expressions rationnelles.

12
12 Automates à pile q0 est son état initial et F ⊆ Q est l’en-
semble des états finaux, s’il existe un calcul
12.1 Langages reconnaissables par (q0 , γ0 ) − u1 ...un → (qn , αn ) d’origine (q0 , γ0 )
automates à pile tel que :
Un automate à pile est une machine munie 1. reconnaissance par état final : qn ∈ F ;
d’une bande de lecture, d’une bande de travail 2. reconnaissance par pile vide : αn = ;
organisée en pile, et d’un contrôle. Donnez di-
rectement l’automate qui reconnait an .bn On note par Lang(A) le langage des mots re-
connus par l’automate A. Notons l’importance
Definition 21 Un automate à pile non-
du symbole de fond de pile : la première tran-
déterministe A est un quadruplet (Σ, Q, Γ, δ) où
sition de l’automate nécessite la lecture d’un
1. Σ est le vocabulaire de l’automate symbole dans la pile, qui doit donc être initia-
2. Q est l’ensemble des états de l’automate ; lisée avec γ0 .
3. Γ est le vocabulaire de pile de l’automate ;
4. δ : Q × (Σ ∪ {}) × Γ → P (Γ? × Q) est la
Theoreme 11 Les modes de reconnaissance
fonction de transition de l’automate.
sont équivalents pour les automates non
L’automate sera dit déterministe s’il vérifie déterministes.
qu’il n’y a jamais de choix possible. Les epsilon
transitions peuvent être déterministe, à condi- Preuve : Soit A un automate à pile reconnais-
tion que le symbole de pile ne soit pas utilisé sant par état final. On construit un automate
dans d’autre transitions de l’état concerné. reconnaissant à la fois par état final et pile
On notera q − a, X, α → q 0 pour (q 0 , α) ∈ vide : il suffit pour cela d’ajouter de nouvelles
δ(q, a, X). Lexicographie les lettres a, b, c, . . . transitions sur chaque état final de manière à
pour les lettres de Σ , les lettres u, v, w, . . . vider la pile. Cette transformation ne préserve
pour les mots sur Σ, les lettres X, Y, Z pour les pas forcément le déterminisme (si il y a des
lettres de Γ et les lettres α, β . . . pour les mots transitions qui partaient de l’état final). Soit
de pile sur Γ maintenant A un automate à pile reconnais-
sant par pile vide. On construit un automate
Definition 22 Étant donné un automate A =
reconnaissant à la fois par état final et pile
(Σ, Q, Γ, δ) on appelle configuration toute paire
vide, en ajoutant un nouvel état f final, un
(q, α) formée d’un état q ∈ Q de l’automate
nouveau symbole de fond de pile γ00 , puis
et d’un mot de pile α ∈ Γ? . On appelle tran-
les transitions : qui commencent par empiler
sition de l’automate, la relation entre confi-
ce nouveau fond de pile dessous l’ancien, et
gurations notée (q, α) − a, X, β → (q 0 , α0 ), où
ensuite l’utilise pour aller vers f
a ∈ Σ, X ∈ Γ, β ∈ Σ? ,telle que (i)(q 0 , β) ∈
(i)delta0 (q00 , γ0 ) = (q0 , γ00 γ0 );
δ(q, a, X), (ii)α = λX, et(iii)α0 = λβ
(ii)∀q ∈ Q∀a ∈ Σ ∪ {}∀X ∈ Γ, δ 0 (q, a, X) =
Definition 23 Étant donné un automate A δ(q, a, X);
= (Σ, Q, Γ, δ), on appelle calcul d’origine (iii)∀q ∈ Q, delta0 (q, γ 0 0) = (f, ).
(q0 ∈ Q, α0 ∈ Γ+ ,une suite de transitions Ces transformations conservent le
(q0 , α0 ) − a1 , X1 , β1 → (q1 , α1 )...(qn−1 , αn−1 ) − déterminisme. Comme le déterminisme
an , Xn , βn → (qn, αn ). L’entier n est la lon- est conservé en passant de la reconnaissance
gueur du calcul et a0 a1 ...an est le mot lu par le par pile vide à celle par état final, la bonne
calcul, en abregé (q0 , α0 ) − a0 ...an → (qn , αn ) notion de reconnaissance par un automate
déterministe, c’est-à-dire celle qui qui autorise
Plusieurs notion de reconnaissance. toutes la plus grande classe de langages reconnus,
équivalentes, est basée sur la reconnaissance par état final.
On choisit la reconnaissance par état final
Definition 24 On dit que le mot u = u1 ...un pour les automates déterministes. (si on a
est reconnu par l’automate A + q0 , F, γ0 où déterministe + état final, on ne peut pas en
γ0 ∈ Γ est appelé fond de pile de l’automate, déduire déterministe + pile vide)

13
12.2 Automates à pile et grammaires q, γ0 , m− >∗ q, Xα, v et m = u.v est un mot
hors-contexte du langage de la grammaire.
2-Montrons que Algébrique est inclus dans
Les langages reconnaissables par un auto- Hors-contexte : C’ est plus complexe, et sans
mate à pile (possiblement non-déterministes) intérêt pratique : nous l’omettrons.
sont appelés algébriques. Un langage est hors
contexte s’il est généré par une grammaires
hors-contexte. 13 Démontrer qu’un langage
Theoreme 12 Un langage est hors-contexte si
est ou n’est pas algébrique
et seulement si il est algèbrique.
13.1 Forme normale de Chomsky
Preuve : on utilise la double inclusion. Theoreme 13 Pour tout langage hors-
1- Montrons que HorsContexte est inclus dans contexte L, il existe une grammaire
Algébrique. propre G qui l’engendre dont toutes les
Pour reconnaitre le langage engendré par règles sont de l’une des trois formes
une grammaire hors contexte, l’idée est de S → , P → a, ouP → M N avec M, N
construire un automate à pile non-déterministe différents de S. (c’est la FNC Forme Normale
qui calque le calcul fait par la grammaire : Chomsky)
Exemple pour la grammaire S →
epsilon|aSb on a la dérivation S → aSb → Preuve : Partant d’une grammaire hors-
aaSbb → aaaSbbb → aaabbb. A l’étape aaSbb contexte propre G = (ΣT , ΣN , S, R), on
le préfixe du mot reconnu sera le début du mot commence par rajouter une copie de ΣT à
généré jusqu’au premier non terminal, c’est a ΣN (on notera A la copie de a), puis l’en-
dire : aa , la pile contiendra le reste : c’est a semble de règles A → a|a ∈ Σ . On rem-
dire Sbb. Pour se faire, juste dans cette preuve, place ensuite les symboles terminaux a figu-
on convient que la pile tombe à gauche, (au rant dans les membres droits de règles ini-
lieu de a droite comme d’habitude) ; tiales par le non-terminal correspondant A,
L’automate a un unique état , on l’appelle puis on remplace récursivement la règle X →
automate ”marguerite” X1...Xn pour n > 2 par X → X1Y etY →
règle : (epsilon, S,aSb) (a,a,epsilon) X2...Xn en ajoutant un nouveau non-terminal
(b,b,epsilon) Y à chaque fois. La FNC est utilisée pour
au début, on dépile S on empile aSb démontrer un théoréme de pompe pour les lan-
ensuite, on dépile a en lisant a gages algébriques. Exemple : donner la FNC
ensuite on dépile S on rempile aSb de la grammaire S → , S → aSb attention, il
ensuite a nouveau on dépile a en lisant a faut introduire un nouvel axiome, pour obte-
ensuite on dépile S on rempile que d’al. nir une grammaire propre, car dans une gram-
ensuite on depile les 2 b en lisant les 2 b. maire propre, l’axiome n’apparaı̂t pas en partie
Dessiner l’automate à pile correspondant. droite.
Preuve cas général soit G = (ΣT , ΣN , S, R),
on construit un automate à pile A = (ΣT , Q =
13.2 Pompage des algébriques
{q}, q, ΣN ∪ ΣT , S, T ) qui reconnait L(G) par
pile vide. l’alphabet de pile contient non termi- Expliquer sur S → aSb| le principe du pom-
naux ET terminaux. page (on re-génére S depuis S).
À toute règle de la forme N → β, on fait Revenons à notre grammaire de règles S →
correspondre la transition q − , N, β → q , S → aSb engendrant les mots de la forme
Pour tout terminal a on utilise la règle q − an bn , et considérons l’arbre syntaxique du
a, a, → q Une récurrence simple montre mot ab : Le long du chemin central, le non-
que les dérivations dans la grammaire cor- terminal S apparaı̂t deux fois. On peut donc
respondent très exactement aux calculs de obtenir de nouveaux arbres syntaxiques pour
l’automate. Plus précisément, la grammaire la même grammaire en supprimant, ou en
dérive S− >∗ uXα− >∗ m si et seulement répétant un nombre arbitraire de fois le mo-
si l’automate peut générer la configuration tif central S(a, , b). Par exemple on en peut

14
déduire que le mot aabb appartient au langage. décomposition quelconque, comme |xvy| < N
etc il ne peut contenir à la fois a, b et c

Theoreme 14 Si L est algébrique, alors il sa-

tisfait la propriété 13.3 Clôture
∃N ∈ N tel que
— Clos par union S → S1|S2
∀m ∈ L vérifiant |m| ≥ N,
— Clos par étoile S → S.S1|
∃u, x, v, y, w ∈ Σ?T tel que m = uxvyw et
— Pas clos par intersection !.
|xy| > 0 et |xvy| < N
— Pas clos par complémentaire ! !.
et on peut pomper, c’est à dire ∀i ≥ 0 on a
— Clos par intersection avec rationnel
uxi vy i w ∈ L.
— Cloture par morphisme, morphisme in-
Preuve : on choisit une grammaire G = verse (rappeler ce qu’est un morphisme)
(ΣT , ΣN , S, R) en forme normale de Chomsky Attention, l’intersection de deux langages n’est
qui engendre le langage L. pas algébrique contre exemple an bn cm et
m n n n n n
Lemme si N est le nombre de non-terminaux a b c intersecté donne a b c . Pour mon-
dans une grammaire Chomsky, et un arbre trer que l’intersection avec un rationnel reste
syntaxique a une hauteur h, alors le mot des algébrique, on fait le même produit synchro-
feuilles est de longueur 2h − 1 au plus. nisé qu’on a déjà vu dans le cadre des auto-
Preuve du Lemme par récurrence. mates d’états fini. Ce produit ne marche pas
h
cas h = 1 une branche 2 − 1 = 1. pour l’intersection de deux langage algébriques,
Cas h+1 on applique la formule sur chacun des car on obtiendrait deux piles à gérer, et on
deux sous arbres dont la profondeur est h ne peut gérer deux piles avec une seule pile ;
Preuve pompe. On choisit N = 2|ΣN |+1 . si Le complémentaire d’un algébrique, n’est pas
un mot m a une longueur≥ N alors d’apres algébrique, sinon l’intersection le serait. Exer-
le Lemme précédent, son arbre de dérivation a cice : exprimer l’intersection à partir de l’union
une hauteur ≥ |ΣN | + 1. On choisit un sous- et du complémentaire.
arbre de profondeur EXACTEMENT ΣN + 1.
soit C un chemin dans cet arbre de taille
|ΣN | + 1. il existe deux nœuds étiquetés par le 14 Analyse syntaxique ascen-
même non-terminal A (faire dessin). On a une dante
première dérivation S− > uAw une deuxième
A− > xAy ensuite le deuxième A se réécrit 14.1 C’est quoi l’analyse ascen-
à son tour A− > v. On peut ici supposer dante ?
sans perte de généralité que u, x, v, y, w ne
contiennent que des terminaux (s’il contiennent On construit l’arbre de dérivation en partant
aussi des non terminaux, on les réécrit jus- des feuilles vers la racine. L’analyse descen-
qu’au bout). Si on veut pomper k fois, il dante vue en PIL l’an dernier, construit l’arbre
suffit d’intercaler k − 1 réécritures récursives de la racine vers les feuilles. Les grammaires qui
supplémentaires A− > xAy avant de faire la marchent pour l’analyse Descendante (resp. as-
réécriture non récursive A− > v. cendante) s’appelle LL(1) premier L : left pour
On doit rappliquer le lemme encore une fois : mot lus de gauche a droite, deuxième L= Left
Grâce au fait qu’on a choisit un sous-arbre de pour dérivation gauche (resp. LR(1) le R veut
profondeur EXACTEMENT |ΣN | + 1, le mot dire Right pour dérivation droite). Le chiffre 1
xvy qui est un sous mot des feuilles de ce signifie un caractère d’avance.
sous arbre a une longueur inférieur ou égale à Une grammaire qui peut se compiler vers un
2ΣN +1 = N , yes. analyseur descendant, peut toujours aussi se
Comme pour les rationnels, on utilise la compiler vers un analyseur ascendant, mais pas
contraposée de la pompe, pour montrer qu’un le contraire. En d’autre mots, LL(1) est inclus
langage n’est pas algébrique. Exemple ap dans LR(1), mais pas le contraire. l’analyse as-
, p premier n’est pas algébrique. (même cendante est donc plus générale que l’analyse
démonstration que pas rationnel) an bn cn n’est descendante. C’est celle utilisée en vrai dans
pas algébrique. je choisis u = aN bN cN et une les compilateur.

15
14.2 L’automate à un seul état. Construction de l’automate Magique :
— item=règle + point dedans (ou on est
Considérons comme exemple fil conducteur,
dans la règle)
la grammaire simplissime S− > aSb|
— états = ensemble d’items
L’automate d’analyse ascendante se — clôture d’un ensemble d’item : Règle du
construit ainsi : Soit G = (ΣT , ΣN , S, R) ”rebondissement”.
la grammaire hors-contexte qui nous — transition : on déplace le point,
intéresse, et qui est cette fois augmentée Règle du rebondissement : Si un état contient
de la règle S 0 → S# . On rajoute aussi le l’ item M → α.N β ou N est non terminal alors
caractère # à la fin du mot. L’automate est on rajoute tout les item N → .γ pour toute
A = (ΣT ∪ {#}, ΣN ∪ {S 0 }, γ0 , {1, 2}, {2}, T ) , règle N → γ de G ; Attention : on peut re-
où la fonction de transition T est définie par : rebondir, et re-re-rebondir etc...
— shift : 1 − a, , a → 1 pour tout a ∈ Σ . Transition par une lettre x : dans tous les
— reduce : 1 − , w, N → 1 pour toute règle items ou y a un point avant le x, on déplace le
N → w ∈ R (on dépile un mot w et on point aprés le x, et on recopie ces (potentielle-
empile N ) ment plusieurs) items modifiés dans un nouvel
— succès 1 − , S#, S 0 → 2 descendant état, après quoi, on cloture, et on rebondit, re-
L’automate ascendant à deux états avec le rebondi et re-re-rebondi . . .L’ensemble de ces
formalisme d’automate a pile, l’état 2 est fi- états et de ces transition constitue ce qu’on ap-
nal. Ecrire cet automate pour notre exemple pelle l’automate LR(0).
fil conducteur, en notant des action reduce et Faire l’automate LR(0) de l’exemple. Cet au-
shift. Faire tourner cet automate, pour analyser tomate reconnaı̂t les mots de pile d’une ana-
la chaine aabb. Ecrire la pile a gauche le mot a lyse réussie. Constater que cela fonctionne sur
droite, et une colonne pour les actions. l’exemple ; Réécrire les états avec juste un
L’automate est non-déterministe puisque numéro, en les mettant tous finaux ; On trouve
lecture et réduction S− > . peuvent le langage de pile S + S# + a? + a? S + a? Sb
être fait simultanément. On parle de conflit
lecture/reduction. Il y aussi des conflits Theoreme 16 Si on fait tourner l’automate
réduction/réduction entre S− > et S− > pour reconnaı̂tre un mot m mélangeant termi-
aSb. L’automate ne peut être déterministe naux et non terminaux, et que on ne bloque pas,
qu’en l’absence de tels conflits. m est un mot de pile possible. De plus, si on ar-
Enlever le non déterminisme = dire s’il faut rive dans un étant q, il doit contenir un item
lire ou réduire, et pour réduire, avec quelle N → α.β tel que α est suffixe de m , m =
règle, (peut y en avoir plusieurs). On dira que m0 α et il existe t un mot de terminaux et une
l’on ”résous des conflits”. Les conflits peuvent dérivation droite de S− > m0 N t− > m0 .α.β.t
être entre un shift et un reduce, ou entre deux
actions reduce ; Nous allons les résoudre grâce Ce théorème renseigne sur le prochain pas à
à deux techniques : faire pour réaliser l’analyse ascendante de mβ
1. Un automate ”MAGIQUE” dont les états qui remonte la dérivation.
vont déjà préciser quelles sont les actions 1. si β = alors α est appelé un ”manche” de
possible shift ou reduce ; l’analyse ascendante, i.e. la dernière étape
2. La lecture d’un caractère d’avance. de la dérivation droite est de la forme
N → α. On en déduit que la prochaine
étape de l’analyse ascendante (qui va dans
14.3 L’automate Magique. l’autre sens) est l’action reduce(N → α).
Theoreme 15 le langage des mot de pile pos- Plus généralement, on pourra faire une
sible est un langage régulier. On peut facile- action reduce (N → α.) depuis un état
ment construire l’automate d’état finis ”ma- donné, seulement si l’état contient un item
gique” le reconnaissant. L’état dans lequel on N → α. avec le point au bout,
se trouve après lecture du début du mot, ren- 2. si au contraire β 6= , la prochaine étape
seigne sur l’action qu’il faut faire pour la pro- de l’analyse doit augmenter la pile en pous-
chaine étape d’analyse ; sant la première lettre de β sur la pile. En

16
en déduit que l’on peut faire des shift a on constate que cela marche parce-que sui-
seulement si l’état contient un item avec vant (S)={b, #}, ne contient pas la lettre a.
la lettre a précédée du point. L’automate ainsi que la grammaire s’appelle
”SLR(1)”.
14.4 L’automate Super-Magique
14.6 Premier et suivant (vu en PIL)
Les deux sortes d’actions possible dans un
état donné sont donc : On définit deux sortes d’ensemble de lettres
1- reduce ( X → α. ) si il y a un item x → α. associés aux non-terminaux :
avec un point final. premier(N ) = {a ∈ ΣT |∃β ∈ Σ? N → aβ}
2- shift a (lecture en francais), si y a un item premier(α ∈ Σ? ) = {a ∈ Σ? |∃β ∈ Σ? , α → aβ}
avec la lettre a après le ’.’ suivant(N ∈ V ) = {a ∈ Σ|S → αN aβ}
Ces ensembles se calculent en résolvant
L’automate magique, en cache un autre ”Su- un système d’equations (fait en TD) Cette
perMagique” qui manœuvre l’automate ma- résolution, se fait en itérant une fonction jus-
gique. Il gére une pile intercalant les états du qu’à obtention d’un point fixe. On utilise pour
magique entre les symboles de piles incluant cela le théorème du point fixe de Kleene, qui
terminaux et non-terminaux. Ces états sont s’énonce comme suit :
utilisé avec l’algo suivant :
— Empile l’ état courant avant de faire un Theoreme 17 Soient L un ensemble munit
shift. un ordre partiel complet, 0 son élément mi-
— L’état empilé avant α est utilisé sur une nimum, et f : L → L une application crois-
action reduce (N → α), sante qui conserve les bornes sup. Alors f a un
— Il est utilisé en faisant une transition de plus petit point fixe qui est le sup de la suite
l’automate magique sur N vers le nouvel croissante suivante : 0 <= f (0) <= f 2 (0) <=
état qui sera empilé aprés N . ... <= f n (0) . . .
Faire fonctionner l’automate super-magique
sur l’exemple. On note que il y a toujours deux Précisons que un ordre partiel complet est un
états ou il a le même conflit shift a / reduce ensemble partiellement ordonné qui possède un
S → précedement évoqué ; Donc on n’a pas élément minimum, et dont toutes les chaı̂nes,
finit de résoudre le non-déterminisme ; (suite de valeurs croissantes) ont un sup.
Preuve : Elle est relativement simple et mar-
rante ; Appelons c = 0 <= f (0) <= f 2 (0) <=
14.5 Le caractère d’avance SLR(1)
... <= f n (0) . . ., la chaine infinie Le fait que f
Sur les états où il y a un conflit shift/re- soit croissante assure que c est croissante car
duce, on essaie de résoudre les conflits de la 0 <= f (0) ⇒ f (0) <= f 2 (0) ⇒ f i (0) <=
facon suivante : on utilise le fait que le mot f i+1 (0). Soit x le sup de c f (x) = f (sup(c)) =
de pile concaténé avec le reste du mot lu, est sup(f (c)) = sup(c) = x. Si y est un autre point
toujours une étape dans la dérivation droite. fixe, alors on montre facilement par recurence
On en déduit que pour pouvoir réduire par que y > f i (0) pour tout i donc par définition
X → beta, le caractère d’avance doit appar- du sup, on aura y > x.
tenir à suivant(X) Exemple : On Aplique donc ce théoreme au
On calcule donc le suivant du non terminal calcul des suivants pour la grammaire : E →
vers lequel on réduit, et on va réduire seulement E + F |F, F → F + G|G, G → id|cte|(E) On
si le caractère d’avance appartient au suivant rajoute S → E# pour être sur que tout le
du non-terminal vers lequel on réduit. Cette monde a un suivant. Ecrire la fonction f , mon-
méthode peut aussi résoudre les confit redu- trer qu’elle est croissante, résoudre l’équation
ce/reduce L’automate avec les réductions plus par itération.
ciblées, s’appele ”l’automate SLR(1)”. Pour Trouver les équation pour les suivants est
mettre en évidence le fait qu’il n’y a plus de plus compliqué que pour les premiers, surtout
conflit, on représente l’automate sous forme en présence de non-terminaux ”annulable”, i.e.
d’un tableau, en indiquant les actions pos- qui peuvent dériver : On éxecute cet algo-
sible dans chaque case ; Sur notre exemple, rithme : Pour chaque non-terminal E, pour

17
chaque occurrence de E dans un membre droits de problème en pratique. (voir exemple donné
des productions, il faut regarder ce qui suit E : à la section suivante, pour comprendre. )
— si c’est un terminal ’x’, ajouter ’x’ à
Suivant(E) 14.9 Différence LALR(1)-LR(1)
— si c’est un non-terminal Y , ajouter Pre-
mier (Y ) à Suivant(E) On va montrer que la grammaire suivante et
— de plus si Y est annulable, reprendre à LR(1) mais pas LALR(1).
partir de ce qui suit Y S ::= (X X ::= F]
— si rien ne suit, ajouter Suivant(A) à S ::= E] E ::= A
Suivant(E), où A est le membre gauchede S ::= F) F ::= A
la production. X ::= E) A ::=
La table de transitions permet de voir sim-
14.7 Le cas LR(1) général plement que cette grammaire est LL(1). Elle
est donc a fortiori LR(1) (résultat du cours
On peut faire mieux que SLR(1). On non démontré). Pour savoir si elle est LALR(1)
améliore en ajoutant une lettre aux items, il faut construire l’automate LR(1). Cet au-
on obtient des nouveaux items, appelés ”item tomate n’a pas de conflits, ce qui permet
LR(1)”. Ce caractère est appelé caractère de de vérifier que la grammaire est bien LR(1).
retour. Il précise quels sont les suivants pos- Il contient deux états l’un formé des items
sible du membre gauche de l’item, en fonction {[F → A., ]], [E → A., )]} l’autre des items
de l’état spécifique de l’automate qui résume {[F → A., )], [E → A., ]]} Dans l’automate
l’historique connu. Pour compacter l’automate, LALR(1) ces deux états ont même structure
on regroupe les item de même structure LR(0), LR(0) et sont confondus en le même état {[F →
donc un item transporte un ensemble de lettres A., )]], [E → A., ])]} qui est conflictuel.
minuscules.
L’ensemble initial d’items est la clôture de
14.10 Génération d’analyseurs syn-
l’ensemble S 0 → .S, #. On rebondit comme
avant, sauf que il faut tenir compte des
taxiques avec YACC
premiéres lettres possibles qui suivent le nom En même temps qu’on reconnaı̂t, on
terminal, au sein de l’item d’ou on rebondit : construit l’arbre de syntaxe abstraite qui est
pour tout item (N → α.Xβ, b) ∈ I, pour toute une version résumée de l’arbre de dérivation,
règle X → γ et tout terminal a ∈ P remier(βb), suffisant pour compiler. Exemple x∗y+3 donne
alors (X → .γ, a) ∈ I. l’arbre sera binop +(binop ∗(id x)(id y))(cte 3)
Regle plus précise qu’avant : Une réduction
N → γ ne pourra être effectuée dans un état
Metode cannonique pour traiter les ex-
q en présence du caractère d’avance a, qu’à
pression arithmetiques : On ajoute des
la condition que q contienne l’item terminal
règles de précédences ou d’associativité per-
(N → γ., a). C’est plus précis que SLR(1),
mettant de désambiguı̈ser automatiquement
car a peut appartenir à suivant de N mais ne
lors du calcul de l’automate LALR (sans trans-
pas être caractére de retour ; car, on l’a déjà
former la grammaire à priori). Les générateurs
dit, l’état spécifique de l’automate permet de
d’analyseurs d’aujourd’hui permettent ce type
préciser l’historique connu.
de désambiguı̈sation (voir TP).

14.8 Le cas LALR(1), utilisé en vrai

par les compilateurs. 15 Machine de Turing
On réduit le nombre d’états en regroupant (Cette partie intègre quelque notes du cours
les états de même structure LR(0) ; i.e. qui d’informatique théorique de Laurent Rozas)
contiennent des items identiques, au caractère
de retour près. C’est l’automate que construit Definition 25 Une machine de Turing est un
Yacc, seul des grammaires très bizarre sont triplet (Q,Σ, δ) Q est l’ensemble des états, Σ
LR(1) et pas LALR(1), donc cela ne pose pas est l’alphabet , avec un symbole spécial ⊥ ”case

18
vide”. δ la fonction de transition : Q × Σ 7→ Pour construire une machine de Turing sans
{G, D} × Σ × Q se tromper, il faut tout d’abord écrire ce type
d’algorithme qui mentionne des ”balayages”,
Une configuration comprends 1- un ruban bi-
puis ensuite faire les transitions, et en même
infini vide presque partout (fonction f de Z
temps, dessiner l’évolution du ruban.
dans Σ ou l’ensemble des x tels que f (x) non
vide est fini) 2- Un pointeur vers une case de
15.1 Langage récursif
ce ruban appelé tête de lecture 3- Un état.
Une transition comporte la lettre lue, la nou- Definition 27 Un langage est dit
velle lettre posée, et le mouvement de la tête de récursivement énumérable si il existe une
lecture ; Pour simplifier l’écriture, si la nouvelle MTD qui le reconnaı̂t, il est dit ”récursif”, ou
lettre est la même que l’ancienne -ce qui arrive ”décidable” si de plus cette MTD s’arrête pour
souvent- on n’indique pas de lettre ; Pour exe- toutes les entrées.
cuter une transition :
1- on remplace la lettre couramment pointée Origine de cette dénomination : si un langage
par la nouvelle lettre spécifiée dans la transi- est reconnaissable par une MTD on peut effec-
tion tivement énumérer les mots. Il existe un pro-
2- on déplace la tete de lecture, 3- On change gramme qui les énumère, i.e. qui les affiche
d’etat. toutes. Idée de la preuve : on imagine que la
machine de Turing peut afficher des caractères
Definition 26 Une machine de Turing est (on pourrais aussi les stoquer sur le ruban). On
dite détérministe, si on a jamais deux transi- utilise la machine de Turing universelle, qu’on
tions possibles simultanément. va voir bientôt, Celle ci peut simuler n’importe
Pour le moment, on ne considère que des Ma- quelle autre machine. On va simuler un nombre
chine de Turing Détérministe (MTD), car le croissant de d’executions, chacune démarrant
non-déterminisme est difficile à appréhender ; sur un nouveau mot. Dés que l’une d’entre elle
Protocole reconnaissance langage : s’arrête et que l’état est final, on affiche le mot
1- On démarre avec un mot, depuis un état ini- sur lequel on avait démarré pour cette execu-
tial q0 , la tête de lecture pointe sur la première tion.
lettre. Comme elle ne ”consomme” pas les lettres
2- On transitionne, jusqu’à ce que cela bloque du mot reconnu, une machine de Turing peut
(plus de transitions possible). facilement boucler. Exemple : la machine q1 −
3- Si l’état dans lequel on se trouve à ce mo- a, D → q1 −∗ b, G → q1− ⊥, D → q2 final ; Elle
ment la, est final, alors le mot est reconnu. reconnaı̂t a mais n’est pas récursive, car elle
Exemple : une machine de Turing boucle si il y a un b a la fin d’un groupe de a ; la
déterministe qui reconnaı̂t an bn cn On uti- tête se met a faire un va et vient infini a gauche
lise la pluspart du temps des transitions qui droite gauche droite gauche .... Le problème si
ne font que bouger la tête, et ne modifie pas le on boucle, c’est que si jamais le mot n’est pas
ruban. dans le langage, on ne le saura jamais, on saura
Algorithme : seulement si le mot est dans le langage.
Remarque simple, et utile pour les exa-
1. On va à droite du mot en vérifiant la forme
mens : un langage est décidable ssi lui et son
a∗ b∗ c∗ (4 état) puis fait des balayages :
complémentaire sont reconnaissable. preuve, on
2. Sur le trajet droite-gauche, on enlevé à fait tourner en même temps les deux machines,
chaque fois le premier ’c’ rencontré (on le il y en a une qui s’arrêtera un jour.
remplace par un dièse) puis le premier ’b’,
puis le premier ’a’ 15.2 Langage non décidables.
3. On repart vers la droite jusqu’à vide
1. Pour les FSA an bn pas reconnu
4. si lorqu’on revient à gauche, il n’y a plus
que des dièses (en passant les dièses, on 2. Pour les automates a piles, an bn cn pas re-
tombe pas sur ’c’ mais sur vide) c’est connu
gagné, sinon on recommence un tour de 3. Pour les MTD, ”pas reconnu”, signifie
suppression. si ca bloque c’est perdu ; ”pas décidable”,

19
Si on ne peut pas décider si un mot donné — Si prog(m) s’arrête, alors Halt accepte
est dans le langage ou pas, cela signifie qu’ il (prog, m) en un temps fini ;
n’existe pas un algorithme qui s’arrête partout, — Si prog(m) ne s’arrête pas, alors Halt re-
et répond oui ou non si le mot est dedans ou fuse (prog, m) en un temps fini.
pas dedans. Il faut donc chercher beaucoup plus NB si prog ne représente pas une machine, que
loin pour exhiber un langage pas décidable, se passe t’il ? Réponse : cela bloque pour des
parce que cela signifie qu’on ne peut pas cal- raisons de syntaxe.
culer. Notons que cette machine Halt est une
machine universelle, elle doit pouvoir simuler
15.3 Machine universelle d’autres machines via leur code ; On construit
une MTD ”diagonale” qui utilise Halt, et ra-
Il faut considérer un langage dont les mot joute quelques états (faire cela au tableau).
codent des machine de Turing ayant certaines Diagonale prends un entrée un code de MTD
propriétés. Notion de codage, il faut commen- x :
cer par coder l’alphabet de la machine, puis co- diagonale(x) : si Halt accepte (x, x) boucle
der chaqué état chaque transition, et egalement infinie sinon accepter
la configuration initiale.
Mais, on obtient une contradiction pour
l’entrée x =diagonale. En effet, diago-
Definition 28 Une machine de Turing uni-
nale(diagonale) boucle si et seulement si Halt
verselle, est une machine capable de simuler
accepte (diagonale, diagonale) si et seulement
toutes les autres à partir d’un codage.
si diagonale(diagonale) termine. Cela prouve
donc par l’absurde que Halt n’existe pas.
Appelons un tel langage de mot codant
ex de problèmes indécidable simple : savoir
des machines, un ”langage de ”machine”.
si une grammaire n’est pas ambiguë. (on peut
On construit des langage indécidable en
le faire au cas par cas, mais il faut de l’in-
considérant de tels langages de machines. NB
telligence a chaque fois.) exemple marrant is-
on pourrait aussi dire un ”langage de program-
sus des math : une équation diophantienne
mation”, parce-que pour une machine univer-
(a coefficients entiers) admet-elle une solution
selle simulant une autre machine quelconque
entière ? ; C’est le 10éme problème de Hilbert
M , M est comme un programme.
(1900). Matiyasevich prouve qu’on ne peut pas
décider (1971).
15.4 Le problème de l’arrêt Exercice : Montrer que l’ensemble des
On parle de problème indécidable plutôt mots représentant des machine de Turing qui
que de langage indécidable. Puisque les mots s’arrêtent est reconnaissable. on peut répondre
représentent des machines, on parle d’un OUI si cela s’arrête, on ne peut pas savoir si
problème portant sur une propriété des ma- cela ne s’arrête pas.
chines. la star des problèmes indécidable = la
machine encodée va t’elle s’arrêter, ou va t’elle 15.5 La thèse de Church Turing
boucler ?
On montre que tous les modèles de calculs
Theoreme 18 Le problème de l’arrêt est usuels qui semblent plus expressif, sont pour-
indécidable. tant équivalent à la machine de Turing, du
point de vue de la décidabilité puis dans le pro-
Le langage des mots représentant des couples chain chapitre du point de vue de la calculabi-
machine + état initial du ruban, qui s’arrêtent, lité.
n’est pas décidable. Point de vue de la décidabilité : Le fait qu’on
Preuve par l’absurde : (la preuve la plus sache répondre oui ou non, ne dépends pas du
célébre de l’informatique) Supposons qu’il modèle de machine utilisé ;
existe un programme surnmommé ”Halt” qui Modèle 1 : Les machine RAM. Elles ont un
décide le problème de l’arrêt. C’est à dire : nombre fixe de N cases contenant des instruc-
— Halt prends un programme prog, et une tions, un nombre infini de cases mémoire dont
entrée m (son entrée est en deux parties) l’une est distinguée et s’appelle R, ces cases

20
contiennent des entiers arbitrairement grand. autre. Si ce mot utilise des chiffres, on va cal-
Les instructions réalisent des calculs en utili- culer une fonction de N dans N.
sant R et une case de la mémoire désignée par
une adresse. Par exemple l’instruction store x, Definition 29 Une MTD M calcule une fonc-
range le contenu de R dans la case d’adresse x. tion f : D ⊂ Σ? 7→ Σ? si lorsque le ruban
Intérêt : c’est plus expressif, on n’a pas besoin démarre avec x ∈ D, lorsque la machine M
de se promener tout le temps sur le ruban, on blocque f (x) est écrit sur le ruban.
peut directement adresser des cases.
Alternativement, on s’arrête non pas quand
machine RAM = langage assembleur hy-
la machine bloque, mais lorsque elle rentre dans
per simplifié pour usage théorique. Elle sert
un état final. Exo de td, montrez que ces deux
à démontrer que la possibilité d’adresser ne
définitions sont équivalentes. Résultat simple et
change pas la décidabilité.
marrant sur l’existence de fonctions non calcu-
Modèle 2 : des programmes écrit dans un lan- lables :
gage évolué, par exemple C++ tournant sur un
ordinateur avec mémoire infinie (sinon c’est un Theoreme 20 Soit la fonction max qui à n
automate d’états fini). associe le max des temps pris par toutes les
Point technique, la machine RAM opère sur machines de n états, qui ne prennent rien en
des entiers. On peut coder des mot par des en- entrée et qui s’arrêtent. max n’est pas calcu-
tiers (il faut les dénombrer) et vice versa. Par lable.
exemple si l’alphabet à deux lettres O et 1, les
mots seront les nombres écrit en binaire. Preuve : si elle l’était, le problème de l’arrêt
serait décidable. Il suffirait de simuler une ma-
Theoreme 19 Les machines de Turing, les chine de n états, un nombre de pas egal à
machines RAM, les programme C++ sont max(n) ; si elle ne s’est toujours pas arrêtée elle
équivalents du point de vue de la la décidabilité. ne s’arrêtera plus par définition de max.
Décidabilité = calculabilité pour des fonc-
preuve : C++ simule Turing qui simule RAM tions booléennes. On parlera à présent, lors-
qui simule C++. qu’on le peut, de fonctions et de calculabi-
1- C++ simule Turing : on écrit un programme lité, plutôt que de fonction booléennes et de
C++ qui simule une machine de Turing. décidabilité, car. . .c’est plus parlant.
2- RAM simule C++ : c’est un compilateur
3- Turing simule RAM : Il faut coder l’état 16.2 Les machine de Turing Non
d’une machine RAML sur un rubant de Tu- Déterministes.
ring. On réprésente R, et la suite des contenu
Definition 30 Une machine de Turing Non
des cases mémoire. le programme lui, est trans-
déterministe a plusieurs transitions possibles,
formé en un diagramme d’états, en utilisant
pour certaine configurations . Pour que un mot
plusieurs états pour interpréter chaque instruc-
soit reconnu, il suffit que une exécution parmi
tion.
tous celles possibles, mènent vers un état final.
Thèse de Church Turing : toute machine cal-
culante et équivalente a la MT Intuitivement, une MTND est une MTD avec
Ce Postulat n’a jamais été contredit, mais un oracle qui guide le bon choix a faire, lors-
il est par nature indémontrable, donc on ap- qu’il y a un choix. Pour résoudre un problème,
pelle cela la thèse de Church Turing, et pas le une MTND a juste besoin de vérifier qu’une
théorème de Church-Turing. solution potentielle est bien une solution, car
l’oracle peut écrire la solution ;

16 la NP complétude Theoreme 21 On peut simuler une MTND

par une MTD
16.1 Calculabilité
On fait une exploration en largeur d’abord de
On peut facilement faire plus que reconnaı̂tre l’arbre des exécutions, cela oblige à représenter
des mots avec des MTD : On peut calculer des les états de plusieurs machine sur un seul ru-
fonctions de mots, qui associent un mot à un ban. ca va prendre un temps exponentiel. Donc

21
NP est inclus dans EXP qui dénote la classe des Preuve : Au temps t, on a besoin de parcourir
problèmes qui prennent un temps exponentiel. le ruban seulement un nombre de fois fini pour
On ne s’intéresse à partir de maintenant simuler une opération de 1bit du programme
qu’aux machines de Turing qui s’arrêtent tout C++. D’autre part, au temps t, l’espace occupé
le temps, et donc aux ensembles décidables re- est < t plus la taille du mot initialement sur
connus par elles. le ruban. donc la simulation du pas de temps
numéro t, de C++, prends au max t unité de
16.3 Complexité polynomiale, expo- temps. La somme des entiers de 1 à n est de
nentielle l’ordre de n2 . (Faire le détail des calculs au ta-
bleau)
On défini la complexité, d’abord pour une Finalement un programme C++ calcule f
exécution, ensuite pour un programme en en temps polynomial ssi la MT aussi, ce qui
considérant un ensemble de données de taille change c’est juste le degré du polynôme. Idem
n, ensuite pour un problème, en considérant le pour exponentiel, car exp(t)∗exp(t)=exp(2t).
programme le plus rapide qui le résout. Les notions de complexité en temps poly-
Definition 31 On appelle complexité en nomiales et exponentielles ont donc en sens
temps d’une exécution d’une machine de indépendamment de la machine considérée.
Turing le nombre de transitions effectuées lors
Definition 33 Classe P = probleme polyno-
de cette exécution ; et complexité en espace
miaux en temps, indépendamment de la ma-
le nombre de cases de la bande qui ont été
chine Classe EXP = idem, mais exponentiel,
utilisées pendant l’exécution. La complexité en
temps de l’exécution d’un programme C++ le Exemple de problèmes de la classe P : pro-
nombre d’opérations effectuées sur des bits, et duit matrice vecteur, matrice matrice, tri bulle.
complexité en espace le nombre de bits utilisé Exemple de problèmes de la classe EXP : ex-
lors de l’exécution. ploration de l’espace des config d’un jeu, après
N coups.
On considère le max (c’est ce qu’on appelle
communément la complexité au pire) pour un
ensemble de données de taille n. On calcule la 16.4 La fameuse classe NP
complexité à un facteur constant prés (notion Complexité pour une MT non déterministe :
de grand O) On peut alors parler de MTD de on considère l’exécution la plus rapide qui re-
complexité linéaire quadratique, polynomiale, connaı̂t un mot, parmi toutes les exécutions
exponentielle,... d’un programme. possibles.

Definition 32 Soit f une fonction calculable, Definition 34 Classe NP = polynomiaux en

on appelle complexité par MTD, (resp. par temps pour une machine NON DETERMI-
C++), de f , la complexité de la MTD, (resp. NISTE
du programme C++) le plus rapide calculant f ,
lorsque les données de f ont une taille n. NP= dieu écrit la solution, on a juste à la
vérifier, et ce en un temps polynomial. C’est
Exemple le tri de n entiers a une complexité plus facile de vérifier une solution, que de la
nlog(n). Puisque l’on a une équivalence Turing- trouver.
C++ pour la calculabilité, on voudrait aussi Exemple : le problème des équations dio-
des équivalences sur les complexités. Notation : phantiennes, si les solutions sont restreintes
Soit f une fonction calculable, on note CT(f ) a des entiers codés sur n bits, devient NP,
et CP(f ) les complexités de f respectivement construire la machine qui propose une solution
par Turing et par C++ On peut clairement avec quelques états. Quelque inclusions simple :
simuler une MTD par un programme C++ P est dans EXP : trivial
qui aura la même complexité, la complexité NP est dans EXP : déjà démontré, cf simula-
par C++ est donc toujours au moins aussi tion de MTND par MTD
bonne que celle par MTD, c’est-à-dire que l’on P est dans NP : trivial. On ne sait pas si l’inclu-
a CP(f ) ≤ CT (f ). sion est stricte, c’est le grand mystère de toute
On a aussi CT(f ) ≤ CP(f ) .2 l’informatique.

22
16.5 Le problème SAT de la satisfia- Corrolaire : SAT ∈ P ssi P = NP.
bilité preuve=codage : On considère une MT non
déterministe M quelconque, et on introduit un
On se donne des variables (Vi )i ∈ 1 . . . v
tas de littéraux (en nombre polynomial), et un
et une formule logique sur ces variables en
tas de formules (en nombre polynomial) qui si-
forme normale conjonctive. C’est à dire une
mule le fonctionnement de M (un nombre de
formule C1 ∧ C2 ∧ ... ∧ Cc ou chaque Ci est
steps seulement polynomial est nécessaire). On
une clause Ci = Li,1 ∨ Li,2 ∨ ...Li,li , Chaque
s’arrange pour que cette formule vérifie que :
littéral L étant une variable ou sa Négation.
M arrive sur un état final ssi la formule est
Le problème SAT pour SATisfiabilité est de sa-
satisfiable.
voir si l’on peut affecter des valeurs booléennes
De plus, si M fonctionne en temps polyno-
aux variables pour que la formule soit vraie
mial, la taille de la formule est également po-
Exemple, les variables sont V 1, V 2, V 3 et la for-
lynomiale. On a réduit le pb de décider si le
mule (V 1 ∨ V 2 ∨ V 3) ∧ (¬V 1 ∨ ¬V 2 ∨ ¬V 3) ∧
mot est reconnu au pb de satisfaire une formule.
(V 1 ∨ ¬V 2) ∧ (V 2 ∨ ¬V 3) La formule est satis-
La transformation est de nature algorithmique,
fiable en utilisant les assignations : V 1 ← true,
donc elle même faisable avec une machine. Elle
V 2 ← f alse, V 3 ← f alse.
prends également un temp polynomial.
Le problème SAT est clairement dans NP :
On obtient un algorithme non-déterministe po- Soit E ∈NP , soit une machine de Turing M
lynomial qui répond OUI quand la formule est non déterministe qui reconnaı̂t E. il existe un
satisfiable, qui consiste à parachuter les affec- entier F tel que u ∈ E ssi il existe une exécution
tations, puis à vérifier qu’elles forment bien qui reconnaı̂t u en un temps inférieur à |u|F . Le
une solution. Par contre, il ne semble pas que nombre de transitions étant majoré par |u|F , le
SAT soit dans P, l’algorithme naı̈f déterministe pointeur ne pourra se déplacer que sur les cases
consiste à essayer toutes les possibilités, et de B(−|u|F ) à B(|u|F ) ; la case B(0) étant la
comme il y en a 2v , si v est le nombre de va- case pointée initialement. On peut alors définir
riables, on obtient bien un algorithme exponen- un nombre polynomial de variables et écrire
tiel. On a des améliorations de cet algorithme une formule logique de taille polynomiale qui
naı̈f, mais, de fait, tout ce qu’on (on = tous les traduise le fait qu’il existe une telle exécution.
chercheurs en informatique, et même les autres) On a donc les équivalences : u ∈ E
a trouvé comme algorithme reste de complexité ssi Il existe une éxecution de M en moins de
exponentielle. |u|F transitions et qui n’utilise que les cases
B(−|u|F )à B(|u|F ) qui reconnaı̂t u
ssi Une certaine formule logique de taille poly-
16.6 Réduction vers SAT. nomiale en |u| est satisfiable
Qu’est ce qu’une réduction ?. Cette formule s’obtient de la facon suivante :
Les variables sont (on note T = |u|F , “au
Definition 35 Un langage L’ est dit réductible temps t” signifie “après avoir effectué t tran-
en L ssi il existe une MT M de L’ vers L, telle sitions”) :
que pour tout x, M(x) est dans L ssi x est dans — Pour tout état q tout t ∈ 0 . . . N , Q(q, t)
L’. signifie au temps t, on est dans l’etat q”
— Pour tout c ∈ −T . . . T et tout t ∈
Pour savoir si un mot w est dans L0 , le 0 . . . N, P (c, t) qui signifie “au temps t, la
problème se transforme en le test si M (w) est tête de lecture pointe sur la case c”.
dans L, — Pour toute transition f et tout t ∈
Si de plus M fonctionne en temps polyno- 1 . . . T, F (f, t) qui signifie “du temps t − 1
mial, on dit que L0 est polynomial réductible au temps t, on passe par la flèche f ”
en L. — Pour toute lettre l, tout c ∈ −T . . . T
tout t ∈ 0 . . . N, C(l, c, t) qui signifie “au
Theoreme 22 Tout langage NP, est polyno- temps t, la case c contient l”.
mial réductible en SAT. SAT est donc un — Pour tout t ∈ 0 . . . N, A(t) qui signifie ”au
problème avec une sorte d’universalité, on dit temps t, on stoppe et on est en état final”.
que SAT est NP-complet. “Il existe une execution” est alors traduit

23
en un ensemble de clause, dont on donne ici
quelques exemples (Exercice, donnez la liste
complète des clauses)
— A tout moment, on est au moins dans un
état : ∀t, Q(q0, t)∨Q(q1, t)∨...∨Q(q|Q|, t)
— A tout moment, on n’est pas dans deux
états à la fois : ∀t, q = q 0 , ¬Q(q, t) ∨
¬Q(q 0 , t)
— Initialement, le pointeur pointe sur la
case 0 : P (0, 0)
Note : on considère que si l’on est en état final
au temps t0 , alors on n’en bouge plus jusqu’au
temps T , donc on parle tout de même des mo-
ments t avec t ≥ t0 .

16.7 Pourquoi NP-complet veut dire

difficile ?
SAT est NP, de plus il est représentatif de
tout les NP, car il simule une machine de Turing
non deterministe en temps polynomial. Un tel
problème est dit NP complet.
Si SAT est dans P, alors NP=P car tout les
problèmes NP deviennent P, en les simulant
dans SAT.
Si TRUC est NP-complet, alors TRUC ∈ P
ssi P ∈ NP.
Il y a beaucoup,beaucoup d’autre problèmes
qui, tout comme SAT, sont NP-complet : clique
d’un graphe, hamiltonien, homomorphisme de
graphe, voyageur de commerce ; Si on montre
que un pb est NP-complet c’est la preuve qu’il
est difficile, car tous ces problèmes réputés dif-
ficile sont équivalent modulo une réduction po-
lynomiale.

16.8 Exemple de problème NP-

complets
Le problème CLIQUE prend en entrée un
graphe non-orienté G et un nombre k et de-
mande si l’on peut choisir un ensemble E de k
sommets qui forme une clique (i.e. que ∀x, y ∈
E, il y a une arrête entre x et y).
Le problème du voyageur de commerce de-
mande par quelle ville passer, pour minimi-
ser un trajet parcourant un ensemble donné de
villes.

Vous aimerez peut-être aussi

Automates et Langages Formels
Pas encore d'évaluation
Automates et Langages Formels
7 pages
Théorie des Langages Formels en C
Pas encore d'évaluation
Théorie des Langages Formels en C
67 pages
Introduction aux compilateurs et langages
Pas encore d'évaluation
Introduction aux compilateurs et langages
93 pages
Cours Pour L2 LF Pil
Pas encore d'évaluation
Cours Pour L2 LF Pil
25 pages
Introduction à la calculabilité
Pas encore d'évaluation
Introduction à la calculabilité
273 pages
Analyse lexicale en compilation
Pas encore d'évaluation
Analyse lexicale en compilation
164 pages
Cours THL
Pas encore d'évaluation
Cours THL
126 pages
Notions Fondamentales des Langages
Pas encore d'évaluation
Notions Fondamentales des Langages
30 pages
Introduction aux langages formels
Pas encore d'évaluation
Introduction aux langages formels
28 pages
Tla Resume Deepseek
Pas encore d'évaluation
Tla Resume Deepseek
4 pages
Cours THL
Pas encore d'évaluation
Cours THL
79 pages
Automates et expressions régulières expliqués
Pas encore d'évaluation
Automates et expressions régulières expliqués
3 pages
CCMP 1999 Concours
Pas encore d'évaluation
CCMP 1999 Concours
11 pages
Solutions d'exercices sur automates et expressions rationnelles
Pas encore d'évaluation
Solutions d'exercices sur automates et expressions rationnelles
6 pages
Rapport de stage sur OCaml et Coq
Pas encore d'évaluation
Rapport de stage sur OCaml et Coq
21 pages
Rapport sur le simulateur AFD
Pas encore d'évaluation
Rapport sur le simulateur AFD
10 pages
Didactique des mathématiques : enjeux et théories
Pas encore d'évaluation
Didactique des mathématiques : enjeux et théories
5 pages
Opérations sur les automates finis
100% (2)
Opérations sur les automates finis
2 pages
Fondements Logiques en Informatique
Pas encore d'évaluation
Fondements Logiques en Informatique
121 pages
Gvergnaud 1987 Fonction Action Symbolisation Enfant Psychologie
Pas encore d'évaluation
Gvergnaud 1987 Fonction Action Symbolisation Enfant Psychologie
26 pages
Définitions récursives et induction structurelle
Pas encore d'évaluation
Définitions récursives et induction structurelle
34 pages
Bibliothèque de Lautomaticien - 23 - Algèbre de Boole Et Machines Logiques (Jean Kuntzmann, Pierre Naslin) (Z-Library - SK, 1lib - SK, Z-Lib - SK)
Pas encore d'évaluation
Bibliothèque de Lautomaticien - 23 - Algèbre de Boole Et Machines Logiques (Jean Kuntzmann, Pierre Naslin) (Z-Library - SK, 1lib - SK, Z-Lib - SK)
342 pages
Logique Élémentaire - Jb.decrypted
Pas encore d'évaluation
Logique Élémentaire - Jb.decrypted
438 pages
Logique combinatoire en circuits logiques
Pas encore d'évaluation
Logique combinatoire en circuits logiques
1 page
Introduction aux automates finis déterministes
Pas encore d'évaluation
Introduction aux automates finis déterministes
32 pages
Incomplétude et Machines de Turing
Pas encore d'évaluation
Incomplétude et Machines de Turing
15 pages
Logique des Propositions et Systèmes Déductifs
Pas encore d'évaluation
Logique des Propositions et Systèmes Déductifs
95 pages
Ch4 Opérations Sur Les Automates Finis
Pas encore d'évaluation
Ch4 Opérations Sur Les Automates Finis
38 pages
Introduction à la théorie des modèles
Pas encore d'évaluation
Introduction à la théorie des modèles
7 pages
Langages réguliers et automates finis
Pas encore d'évaluation
Langages réguliers et automates finis
8 pages
Automates Finis : Déterministes et Non-Déterministes
Pas encore d'évaluation
Automates Finis : Déterministes et Non-Déterministes
29 pages
Sémantique et Validité en Logique
Pas encore d'évaluation
Sémantique et Validité en Logique
27 pages
TLA - CH01 - Mots Et Langages
Pas encore d'évaluation
TLA - CH01 - Mots Et Langages
6 pages
Analyse lexicale en compilation
Pas encore d'évaluation
Analyse lexicale en compilation
23 pages
Guide Bilingue (Wolof-Français) Mathématiques - CI - 31032024
Pas encore d'évaluation
Guide Bilingue (Wolof-Français) Mathématiques - CI - 31032024
284 pages
Introduction à la linguistique appliquée
Pas encore d'évaluation
Introduction à la linguistique appliquée
3 pages
Différences entre linguistique théorique et appliquée
Pas encore d'évaluation
Différences entre linguistique théorique et appliquée
6 pages
Comprendre la linguistique appliquée
Pas encore d'évaluation
Comprendre la linguistique appliquée
21 pages
Introduction à la linguistique appliquée
Pas encore d'évaluation
Introduction à la linguistique appliquée
7 pages
Analyse des erreurs en linguistique appliquée
Pas encore d'évaluation
Analyse des erreurs en linguistique appliquée
1 page
Introduction à la Compilation et Langages
Pas encore d'évaluation
Introduction à la Compilation et Langages
163 pages
Théorie Des Langages (2/2)
Pas encore d'évaluation
Théorie Des Langages (2/2)
33 pages
Qu'Est-ce Que La Transposition Didactique - Prof Innovant
Pas encore d'évaluation
Qu'Est-ce Que La Transposition Didactique - Prof Innovant
13 pages
Compilation : Exercices et Solutions S5
Pas encore d'évaluation
Compilation : Exercices et Solutions S5
16 pages
Analyse ascendante des chaînes LR(1)
Pas encore d'évaluation
Analyse ascendante des chaînes LR(1)
17 pages
Corrigé Partiel Langages et Automates
Pas encore d'évaluation
Corrigé Partiel Langages et Automates
5 pages
Corrige INFO2 MPI 2023
Pas encore d'évaluation
Corrige INFO2 MPI 2023
28 pages
Exercices de théorie des langages INF208
Pas encore d'évaluation
Exercices de théorie des langages INF208
2 pages
Évaluation d'expressions arithmétiques
Pas encore d'évaluation
Évaluation d'expressions arithmétiques
3 pages
Corrigé des Mines 2017 : Langages et Automates
Pas encore d'évaluation
Corrigé des Mines 2017 : Langages et Automates
7 pages
Introduction à la pensée computationnelle
Pas encore d'évaluation
Introduction à la pensée computationnelle
6 pages
Exercices corrigés en langage SCRATCH
Pas encore d'évaluation
Exercices corrigés en langage SCRATCH
20 pages
Examen Master SVS - UE 34 Décembre 2019
Pas encore d'évaluation
Examen Master SVS - UE 34 Décembre 2019
2 pages
Analyseur lexical et codage Vigenère en Python
Pas encore d'évaluation
Analyseur lexical et codage Vigenère en Python
5 pages
Automates et Langages : Mots et Alphabets
Pas encore d'évaluation
Automates et Langages : Mots et Alphabets
23 pages
Correction TD Langages et Compilation
Pas encore d'évaluation
Correction TD Langages et Compilation
2 pages
Notion de Configuration en Machines de Turing
Pas encore d'évaluation
Notion de Configuration en Machines de Turing
30 pages
Critique de la sémantique formelle
Pas encore d'évaluation
Critique de la sémantique formelle
11 pages
Contrôle continu : Algorithmique du texte
Pas encore d'évaluation
Contrôle continu : Algorithmique du texte
2 pages
ch1 Langages Formels
Pas encore d'évaluation
ch1 Langages Formels
30 pages
Chap 11 Proposition Relatives
Pas encore d'évaluation
Chap 11 Proposition Relatives
2 pages
Introduction aux Automates à Pile (PDA)
Pas encore d'évaluation
Introduction aux Automates à Pile (PDA)
9 pages
L'Expression du But en Français
100% (2)
L'Expression du But en Français
3 pages
Synonymes et contraires en CM1
Pas encore d'évaluation
Synonymes et contraires en CM1
6 pages
Analyse de l'excipit de Germinal
Pas encore d'évaluation
Analyse de l'excipit de Germinal
10 pages
Exercices sur la modalisation et le jugement
Pas encore d'évaluation
Exercices sur la modalisation et le jugement
5 pages
Analyse linéaire de Manon Lescaut
Pas encore d'évaluation
Analyse linéaire de Manon Lescaut
5 pages
Les Figures de Style Décryptées
Pas encore d'évaluation
Les Figures de Style Décryptées
3 pages
Épreuve ministérielle de français 2e année
Pas encore d'évaluation
Épreuve ministérielle de français 2e année
18 pages
Emploi du temps S1 Études Anglaises
Pas encore d'évaluation
Emploi du temps S1 Études Anglaises
5 pages
EBOOK Collectif - L EXPLORATION Du MONDE
100% (1)
EBOOK Collectif - L EXPLORATION Du MONDE
768 pages
Littératures berbères : voix et lettres
Pas encore d'évaluation
Littératures berbères : voix et lettres
57 pages
Test de Niveau - Statistiques, Probabilité, Fonction
Pas encore d'évaluation
Test de Niveau - Statistiques, Probabilité, Fonction
6 pages
Valeurs Des Modes Et Des Temps AP 2
Pas encore d'évaluation
Valeurs Des Modes Et Des Temps AP 2
3 pages
Enjeux de l'enseignement de la traduction
Pas encore d'évaluation
Enjeux de l'enseignement de la traduction
13 pages
Traduction littéraire moderne en traductologie
Pas encore d'évaluation
Traduction littéraire moderne en traductologie
20 pages
Exercices sur l'imparfait 3ème groupe
Pas encore d'évaluation
Exercices sur l'imparfait 3ème groupe
4 pages
Fable de La Fontaine pour 2AM
Pas encore d'évaluation
Fable de La Fontaine pour 2AM
3 pages
Apprendre Le Russe
100% (2)
Apprendre Le Russe
14 pages
Licence Arabe à Distance 2023
Pas encore d'évaluation
Licence Arabe à Distance 2023
14 pages
L'influence du français sur l'anglais
Pas encore d'évaluation
L'influence du français sur l'anglais
177 pages
Types de phrases en français
Pas encore d'évaluation
Types de phrases en français
7 pages
Opérations sur les fractions
Pas encore d'évaluation
Opérations sur les fractions
4 pages
Cours Français
Pas encore d'évaluation
Cours Français
14 pages
Techniques d'analyse littéraire et stylistique
Pas encore d'évaluation
Techniques d'analyse littéraire et stylistique
5 pages
Feux de joie chez les Berbères 1921
Pas encore d'évaluation
Feux de joie chez les Berbères 1921
523 pages
Méthodologie de la rédaction scientifique
Pas encore d'évaluation
Méthodologie de la rédaction scientifique
46 pages
Vérification de français 2ème média
Pas encore d'évaluation
Vérification de français 2ème média
1 page
Homophones : Séquence CM1 à imprimer
Pas encore d'évaluation
Homophones : Séquence CM1 à imprimer
10 pages
Marqueurs de relation et organisateurs textuels
Pas encore d'évaluation
Marqueurs de relation et organisateurs textuels
18 pages