Centrale Informatique optionnelle MP 2017

Thème de l'épreuve Mots synchronisants
Principaux outils utilisés automates, files, parcours de graphe, logique
Mots clefs mot synchronisant, machine, graphe d'automate, SAT, réduction SAT

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


î. '» Option informatique N

'à, F'
_/ MPO

tnncuuns EENTHHLE-SUPËLEE 4 heures Calculatrices autorisées N

Mots synchronisants

Notations
-- Pour tout ensemble fini E, on note |E | son cardinal.

-- On appelle machine tout triplet (Q, E, 6) où Q est un ensemble fini non vide 
dont les éléments sont appelés
états, E un ensemble fini non vide appelé alphabet dont les éléments sont 
appelés lettres et 5 une application
de Q >< E dans Q appelée fonction de transition. Une machine correspond donc à 
un automate déterministe
complet sans notion d'état initial ou d'états finaux.

-- Pour un état q et une lettre :c, on note q.æ : ô(q,æ).

-- L'ensemble des mots (c'est--à--dire des concaténations de lettres) sur 
l'alphabet E est noté E*.
-- Le mot vide est noté 5.

-- On note ua: le mot obtenu par la concaténation du mot a et de la lettre a:.

-- On note 6* l'extension a Q >< E* de la fonction de transition 6 définie par

{W EUR Q, 5*(q58) = q
V(q,oe,u) EUR Q >< E >< E*, 5*(q,oeu) : 5*(6(q,æ),u)

-- Pour un état (1 de Q et un mot m de E*, on note encore q.m pour désigner 
5*(q,m).
Pour deux états q et q', q' est dit accessible depuis q s'il existe un mot 11. 
tel que q' : q.u.

On dit qu'un mot m de E* est synchronisant pour une machine (Q, E, 6) s'il 
existe un état 110 de Q tel que pour
tout état q de Q, q.m : q0.

L'existence de tels mots dans certaines machines est utile car elle permet de 
ramener une machine dans un état
particulier connu en lisant un mot donné (donc en pratique de la « 
réinitialiser » par une succession précise
d'ordres passés a la machine réelle).

La partie I de ce problème étudie quelques considérations générales sur les 
mots synchronisants, la partie Il
est consacrée à des problèmes algorithmiques classiques, la partie III relie le 
problème de la satisfiabilité d'une
formule logique à celui de la recherche d'un mot synchronisant de longueur 
donnée dans une certaine machine
et enfin la partie IV s'intéresse à l'étude de l'existence d'un mot 
synchronisant pour une machine donnée. Les
parties 1, H et 111 peuvent être traitées indépendamment. La partie IV, plus 
technique, utilise la partie Il.
Dans les exemples concrets de machines donnés plus loin, l'ensemble d'états 
peut être quelconque, de même
que l'alphabet (E : {0,1}, {a, b,c} .). Par contre, pour la modélisation en 
Caml, l'alphabet E sera toujours
considéré comme étant un intervalle d'entiers [[O,p -- 1]] où p : |E|. Une 
lettre correspondra donc a un entier
entre 0 et p -- l. Un mot de 2* sera représenté par une liste de lettres (donc 
d'entiers).

type lettre == int; ;
type mot == lettre list; ;

De même, en Caml, l'ensemble d'états Q d'une machine sera toujours considéré 
comme étant l'intervalle d'entiers
[[O,n-- 1]] où n : |Q|.

type etat == int;;

Ainsi, la fonction de transition 6 d'une machine sera modélisée par une 
fonction Caml de signature
etat --> lettre --> etat. On introduit alors le type machine

type machine = { n_etats : int ; n_lettres : int ; delta : etat --> lettre --> 
etat};;

n_etats correspond au cardinal de Q, n_lettres a celui de E et delta a la 
fonction de transition. Pour une
machine nommée M, les syntaxes M.n_etats, M.n_lettres ou M.delta permettent 
d'accéder a ses différents
paramètres. Dans le problème, on suppose que M.delta s'exécute toujours en 
temps constant.

Par exemple, on peut créer une machine M0 a trois états sur un alphabet a deux 
lettres ayant comme fonction
de transition la fonction fO donnée ci--après.

2017-03--06 19:53:58 Page 1/6 (°C) BY-NC-SA

let fO etat lettre = match etat,lettre with
0,0 --> 1

\.

\.

MMD--'HO
|--\OÎ--\O|--\
I
V
MOMOr--\

!
l
l
l
|
]

fO : int --> int --> int = 
let M0 = { n_etats = 3 ; n_1ettres = 2 ; delta = :EO };;

La figure 1 fournit une représentation de la machine M0-

0
0 1
1

Figure 1 La machine M0

On pourra observer que les mots 11 et 10 sont tous les deux synchronisants pour 
la machine M0-

Dans tout le sujet, si une question demande la complexité d'un programme ou 
d'un algorithme, on attend une
complexité temporelle exprimée en O(...).

I Considérations générales

I.A = Que dire de l'ensemble des mots synchronisants pour une machine ayant un 
seul état ?
Dans toute la suite du problème, on supposera que les machines ont au moins 
deux états.
I.B = On considère la machine M1 représentée figure 2. Donner un mot 
synchronisant pour M1 s'il en existe

un. Justifier la réponse.
< - >:_Ï@

CL

Figure 2 La machine M1

I. C = On considère la machine M2 représentée figure 3. Donner un mot 
synchronisant de trois lettres pour
]V[2. On ne demande pas de justifier sa réponse.

I.D = Écrire une fonction delta_etoile de signature machine --> etat --> mot 
--> etat qui, prenant en
entrée une machine M, un état q et un mot u, renvoie l'état atteint par la 
machine M en partant de l'état (] et
en lisant le mot u.

I.E = Écrire une fonction est_synchronisant de signature machine --> mot --> 
bool qui, prenant en entrée
une machine M et un mot u, dit si le mot u est synchronisant pour M.

I .F = Montrer que pour qu'une machine ait un mot synchronisant, il faut qu'il 
existe une lettre x et deux
états distincts de Q, q et q', tels que q.as : q'.æ.

I. G = Soit LS (M ) le langage des mots synchronisants d'une machine M : (Q, 2, 
5). On introduit la machine
des parties M : (Ô, E, 5) où @ est l'ensemble des parties de Q et où 5 est 
définie par

VP c Q, V3: 5 z, â(P,oe) : {5(p,OE), p EUR P}
I.G.1) Justifier que l'existence d'un mot synchronisant pour ]V[ se ramène à un 
problème d'accessibilité de

certain(s) états(s) depuis certain(s) état(s) dans la machine des parties.
I.G.2) En déduire que le langage LS (M ) des mots synchronisants de la machine 
M est reconnaissable.

2017-03--06 19:53:58 Page 2/6 OEC BY--NC-SA

a, c

b, d
Figure 3 M2 : une machine a 4 états

I.G.3) Déterminer la machine des parties associée à la machine M0 puis donner 
une expression régulière du
langage LS(MO).

I.H * Montrer que si l'on sait résoudre le problème de l'existence d'un mot 
synchronisant, on sait dire, pour
une machine M et un état % de M choisi, s'il existe un mot u tel que pour tout 
état q de Q, le chemin menant
de q a q.u passe forcément par (10.

II Algorithmes classiques

On appellera graphe d'automate tout couple (S, A) où S est un ensemble dont les 
éléments sont appelés sommets
et A une partie de S >< E >< S dont les éléments sont appelés arcs. Pour un arc 
(q, x, q"), 35 est l' étiquette de l'arc,
q son origine et q' son extrémité. Un graphe d'automate correspond donc a un 
automate non déterministe sans
notion d'état initial ou d'état final.

Par exemple, avec

2 : {a,b}

SO : {0,1,2,3,4,5}

A0: {(O,b,0),(O,a,3),(0,b,2),(O,a,1),(1,a,l),(1,a,2),(2,b,1),
(2,b,3),(2,b,4),(3,a,2),(4,a,1),(4,b,5),(5,a,1)}

le graphe d'automate GO : (SO, A0) est représenté figure 4.

Soient s et 5' deux sommets d'un graphe (S,/1). On appelle chemin de 5 vers 5' 
de longueur EUR toute suite
d'arcs (sl,oel,s'l), (52,552, sé), ..., (Sg,æz, 52) de A telle que 51 : s, 52 : 
s' et pour tout i de [[1,EUR-- 1]], si : 51+1-
L'étiquette de ce chemin est alors le mot æ1æ2....rg et on dit que s' est 
accessible depuis 5. En particulier, pour
tout 5 EUR S, 5 est accessible depuis 5 par le chemin vide d'étiquette 5.

b

-->

@--

Figure 4 Le graphe d'automate Go

2017-03--06 19:53:58 Page 3/6 («à BY--NC-SA

Dans les programmes à écrire, un graphe aura toujours pour ensemble de sommets 
un intervalle d'entiers [[0, n--1]]
et l'ensemble des arcs étiquetés par E (comme précédemment supposé être un 
intervalle [[0, p-- 1]]) sera codé par
un vecteur de listes d'adjacence V : pour tout 5 E S', V. (s) est la liste 
(dans n'importe quel ordre) de tous les
couples (s', x) tel que (s, au, s') soit un arc du graphe. Pour des raisons de 
compatibilité ultérieure, les sommets
(qui sont, rappelons--le, des entiers) seront codés par le type etat.

Ainsi, avec l'alphabet E = {a, b}, la lettre a est codée 0 et la lettre b est 
codée 1 ; l'ensemble des arcs du graphe
GO, dont chaque sommet est codé par son numéro, admet pour représentation Caml :

VO : (etat * lettre) list vect = [|
[(0,1) ; (3,0) ; (2,1); (1,0)1;
[(1,0) ; (2,0)1;

[(1,1) ; (3,1); (4,1)1;

[(2,0)l ;
[(1,0) ; (5,1)l ;
[(1 , O)]
Il
II.A -- On veut implémenter une file d'attente à l'aide d'un vecteur 
circulaire. On définit pour cela un type

particulier nommé file par
type 'a file={tab : 'a vect; mutable deb: int; mutable fin: int; mutable vide: 
bool}

deb indique l'indice du premier élément dans la file et fin l'indice qui suit 
celui du dernier élément de la file,
vide indiquant si la file est vide. Les éléments sont rangés depuis la case deb 
jusqu'à la case précédent fin en
repartant a la case 0 quand on arrive au bout du vecteur (cf exemple). Ainsi, 
on peut très bien avoir l'indice
fin plus petit que l'indice deb. Par exemple, la file figure 5 contient les 
éléments 4, O, 1, 12 et 8, dans cet ordre,
avec fin=2 et deb=9.

fin deb

i i

12 8 7 2 5 3 1 16 3 4 0 1

Figure 5 Un exemple de file où fin < deb

On rappelle qu'un champ mutable peut voir sa valeur modifiée. Par exemple, la 
syntaxe f . deb <-- 0 affecte la
valeur 0 au champ deb de la file f.

II.A.1) Écrire une fonction ajoute de signature 'a file --> 'a --> unit telle 
que ajoute f x ajoute x a
la fin de la file d'attente f. Si c'est impossible, la fonction devra renvoyer 
un message d'erreur, en utilisant
l'instruction failwith "File pleine".

II.A.2) Écrire une fonction retire de signature 'a file --> 'a telle que retire 
f retire l'élément en tête
de la file d'attente et le renvoie. Si c'est impossible, la fonction devra 
renvoyer un message d'erreur.

II.A.3) Quelle est la complexité de ces fonctions '?

On considère l'algorithme 1 s'appliquant à un graphe d'automate G = (S, A) et a 
un ensemble de sommets E
(on note n : |S| et 00, vide et rien des valeurs particulières).

II.B * Justifier que l'algorithme 1 termine toujours.
II. C * Donner la complexité de cet algorithme en fonction de |S | et |A|. On 
justifiera sa réponse.
II.D * Justifier qu'au début de chaque passage dans la boucle « tant que F 
n'est pas vide », si F contient

dans l'ordre les sommets 51,52, ...,s,., alors D{sl] g D{s2] < < Dis,] et D{sr] 
-- D{51] g 1.

ILE * Pour 5 sommet de G, on note dS la distance de E a 5 c'est--à--dire la 
longueur d'un plus court chemin
d'un sommet de E a 5 (avec la convention ds : oo s'il n'existe pas de tel 
chemin).

II.E.1) Justifier brièvement qu'à la fin de l'algorithme, pour tout sommet 5, 
D{s] # 00 si et seulement si 5 est
accessible depuis un sommet de E et que ds { D{s]. Que désigne alors c ?

II.E.2) Montrer qu'en fait, a la fin, on a pour tout sommet s, D{s] : ds. Que 
vaut alors PLS] '?

II.F * Écrire une fonction accessibles de signature

((etat*lettre) list) vect --> etat list --> int * int vect * (etat*lettre) vect
prenant en entrée un graphe d'automate (sous la forme de son vecteur de listes 
d'adjacence V) et un ensemble
E de sommets (sous la forme d'une liste d'états) et qui renvoie le triplet (c, 
D, P) calculé selon l'algorithme
précédent. Les constantes oo, vide et rien seront respectivement codées dans la 
fonction accessibles par --1,
(--2,--1) et (--1,--1).

2017-03--06 19:53:58 Page 4/6 (°C) BY-NC-SA

créer une file d'attente F, vide au départ
créer un tableau D dont les cases sont indexées par S et initialisées a 00
créer un tableau P dont les cases sont indexées par S et initialisées a vide
créer une variable 0 initialisée a n
pour tout 5 EUR E faire
insérer s a la fin de la file d'attente F
fixer Dis] à ()
fixer Pis] à rien
diminuer c de 1
fin pour
tant que F n'est pas vide faire
extraire le sommet s qui est en tête de F
pour tout arc (s,y, s') EUR A tel que D{s'] : oo faire
fixer Dls'] à D{s] + 1
fixer P{s'] a (s,y)
insérer s' a la fin de la file d'attente F
diminuer c de 1
fin pour
fin tant que
renvoyer (c,D,P)

Algorithme 1

II. G + Écrire une fonction chemin de signature etat --> (etat*lettre) vect --> 
mot qui, prenant en entrée
un sommet s et le vecteur P calculé à l'aide de la fonction accessibles sur un 
graphe G et un ensemble E,
renvoie un mot de longueur minimale qui est l'étiquette d'un chemin d'un sommet 
de E a s (ou un message
d'erreur s'il n'en existe pas).

III Réduction SAT

On s'intéresse dans cette partie a la satisfiabilité d'une formule logique 
portant sur des variables propositionnelles
331, ..., $.... On note classiquement /\ le connecteur logique « et », V le 
connecteur « ou » et f la négation d'une
formule f.

On appelle littéral une formule constituée d'une variable xi ou de sa négation 
.il-, on appelle clause une disjonction
de littéraux.

Considérons une formule logique sous forme normale conjonctive c'est--à--dire 
sous la forme d'une conjonction de
clauses. Par exemple,

F1:(aclVÆ2VOE3)A(æ1Voe4)A(æ2væ3\/æ4)

est une formule sous forme normale conjonctive formée de trois clauses et 
portant sur quatre variables proposi--
tionnelles @, @, mg et 554.

Soit F une formule sous forme normale conjonctive, composée de n clauses et 
faisant intervenir m variables. On
suppose les clauses numérotées cl, 02, ..., en. On veut ramener le problème de 
la satisfiabilité d'une telle formule
au problème de la recherche d'un mot synchronisant de longueur inférieure ou 
égale à m sur une certaine
machine. On introduit pour cela la machine suivante associée à F :

-- Q est formé de mn + n + 1 états, un état particulier noté f et n(m + 1) 
autres états qu'on notera q... avec
(i,j) EUR |Ï1,n]] >< |Ï1,m+ 1]] ;

-- E = {0,1} ;

-- 5 est défini par
. f est un état puits, c'est--à--dire 6(f, O) : 5(f, 1) : f,
. pour tout entier i de [[1, n]], 6(Qi,m+la O) : 5(Qi,m+1a 1) : f,

0 pour tout i dans [[1,n]] et j dans [[1,m]],

f si le littéral a:j apparaît dans la clause ci
q...;1 Sinon

5 0 7 f si le littéral @ apparaît dans la clause ci
(qi--J' >_ q- - sinon
1,j+1

III .A + Représenter la machine associée à la formule F1.

2017--03--06 19:53:58 Page 5/6 (:c BY--NC-SA

III.B * Donner une distribution de vérité (v1,u2, u3,u4) EUR [[0,1]]4 (la 
valeur 1),- étant associée à la variable .r,--)
satisfaisant F1. Le mot u1u2u3u4 est--il synchronisant '?

III. C -- Montrer que tout mot u de longueur m + 1 est synchronisant. À quelle 
condition sur les qm.u un mot
u de longueur m est--il synchronisant '?

III.B * Montrer que si la formule F est satisfiable, toute distribution de 
vérité la satisfaisant donne un mot
synchronisant de longueur m pour l'automate.

II I .E * Inversement, prouver que si l'automate dispose d'un mot synchronisant 
de longueur inférieure ou égale
à m, F est satisfiable. Donner alors une distribution de vérité convenable.

IV Existence

On reprend dans cette partie le problème de l'existence d'un mot synchronisant 
pour une machine M.
IV.A * Soit M : (Q, E, 6) une machine.
Pour toute partie E de Q et tout mot u de E'", on note E.u : {q.u, q E E}.

IV.A.1) Soit u un mot synchronisant de M et u0,u1, ...,u,. une suite de 
préfixes de u rangés dans l'ordre
croissant de leur longueur et telle que ur : u. Que peut--on dire de la suite 
des cardinaux |Q.ui| '?

IV.A.2) Montrer qu'il existe un mot synchronisant si et seulement s'il existe 
pour tout couple d'états (q, q')
de Q2 un mot uq'q, tel que q.uq'q, : q'.uq7q,.
On veut se servir du critère établi ci--dessus pour déterminer s'il existe un 
mot synchronisant. Pour cela, on
associe a la machine M la machine M : (Q, E, 6) définie par :

-- @ est formé des parties a un ou deux éléments de Q ;

-- Sest définie par V(E,æ) EUR Ô>< E, Ë(E) : {5(q,æ), q E E}.

IV.E * Si n : |Q|, que vaut % : |ô| ?

IV. C * On a dit que pour la modélisation informatique, l'ensemble d'états 
d'une machine doit être modélisée

par un intervalle [[0, n -- 1]]. @ doit donc être modélisé par l'intervalle 
[[O,ñ -- 1]]. Soit go,, une bijection de @
sur [[0, ñ-- 1]]. On suppose qu'on dispose d'une fonction set_to_nb de 
signature int --> (etat list) --> etat
telle que set_to_nb n EUR pour n élément de N* et EUR liste d'états renvoie

{an({i}) si EUR = m avec i & [[0,n-- 1]]
«pn({i,j}) si EUR = {ml avec (M") EUR [[OEn-- 1]]2, 1"  etat --> (etat
list) telle que nb_to_set n q pour n élément de N* et q élément de [[O,ñ -- 1]] 
renvoie une liste d'états de la
forme {i] ou {i, j] (avec i < j) correspondant à  etat --> lettre --> etat 
qui prenant en entrée une
machine M, un état q-- de @ et une lettre a:, renvoie l'état de @ atteint en 
lisant la lettre a: depuis l'état (] dans
M.

I V.D * Il est clair qu'à la machine llÎ, on peut associer un graphe d'automate 
5 dont l'ensemble des sommets
est @ et dont l'ensemble des arcs est {(q, a:, 5(q, du)), (q, 33) EUR Ô>< 2}. 
On associe alors à âle graphe retourné Ô'VR
qui a les mêmes sommets que 5 mais dont les arcs sont retournés (ie (q, 35, q') 
est un arc de ÛR si et seulement
si (q',a:,q) est un arc de (?).

Écrire une fonction retourne_machine de signature machine --> ((etat*lettre) 
list) vect qui à partir
d'une machine M, calcule le vecteur Vdes listes d'adjacence du graphe 5R.

I V.E * Justifier qu'il suffit d'appliquer la fonction accessibles de la partie 
H au graphe âR et à l'ensemble

des sommets de 5R correspondant à des singletons pour déterminer si la machine 
M possède un mot synchro
nisant.

IV.F * Écrire une fonction existe_synchtonisant de signature machine --> bool 
qui dit si une machine
possède un mot synchronisant.

Jan Ôernÿ, chercheur slovaque, a conjecturé au milieu des années 60 que si une 
machine a n états possédait
un mot synchronisant, elle en avait un de longueur inférieure ou égale à (n-- 
1)2. La construction faite dans la
partie III afiîrme que la recherche, dans une machine, d'un mot synchronisant 
de longueur inférieure ou égale à
une valeur m fixée est au moins aussi difficile en terme de compleæité que 
celui de la satisfiabilité d'une formule
logique à m variables sous forme normale conjonctive (qu 'on sait être un 
problème « diflîcile »).

oooFlNooo

2017--03--06 19:53:58 Page 6/6 ,@c BY--NC-SA

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique optionnelle MP 2017
Corrigé
Ce corrigé est proposé par William Aufort (ENS Lyon) ; il a été relu par Martin
Guy (ENS Lyon) et Benjamin Monmege (enseignant-chercheur à l'université).

Cette épreuve est consacrée aux aspects théorique et algorithmique des mots 
synchronisants associés à une machine. Une machine se comporte comme un automate
fini, hormis le fait qu'on ignore les états initial et finals. La notion de mot 
synchronisant est importante en théorie des automates et apparaît la première 
fois dans un
problème naturel : comment réinitialiser un système ayant un nombre fini 
d'états sans
savoir dans quel état il se trouve ?
Le sujet comporte quatre parties, dont les trois premières sont indépendantes.
· La première partie étudie quelques propriétés générales des mots 
synchronisants, notamment le fait que l'ensemble des mots synchronisants d'une 
machine
forme un langage reconnaissable. Il y est question à la fois d'étude d'exemples,
de questions d'implémentation plutôt faciles, et de questions utilisant des 
raisonnements proches de ceux sur les automates.
· La deuxième partie, purement algorithmique, a pour objectif l'implémentation
d'un algorithme qui détermine l'ensemble des sommets s d'un graphe d'automate 
accessibles à partir d'un ensemble d'états E donné, ainsi qu'un moyen
d'obtenir un plus court chemin de E à s. Tout d'abord, on implémente une 
structure de file à l'aide d'un tableau circulaire. Puis on étudie un 
algorithme dont le
principe est de parcourir en largeur le graphe, en mettant à jour des structures
supplémentaires permettant de retrouver les plus courts chemins. Cette partie
comporte beaucoup de questions d'implémentation et de questions relatives à
la correction, la terminaison et la complexité des algorithmes.
· Dans la troisième partie, on construit à partir d'une formule booléenne 
quelconque une machine dont on montre qu'elle admet un mot synchronisant d'une
certaine longueur si et seulement si la formule est satisfiable. Cette partie 
mêle
donc des raisonnements de théorie des automates et de logique.
· Enfin, la quatrième partie permet de résoudre le problème de l'existence d'un
mot synchronisant en utilisant la partie II. Elle contient des questions plus
avancées sur les automates et des questions d'implémentation.
Le sujet est très bien écrit et permet de manipuler toutes les notions du 
nouveau
programme d'informatique optionnelle (automates, graphes, algorithmique et 
calcul
propositionnel). Cela en fait un sujet très intéressant pour la préparation aux 
épreuves
d'informatique.

Indications
I.B Raisonner sur la parité de l'état q.m.
I.E Il suffit de vérifier que l'état q.m est le même pour tout état q.
I.F Si u est synchronisant, considérer deux « calculs » partant d'états 
différents
de la machine sur l'entrée u.
b
I.G.1 Reformuler la propriété « admettre un mot synchronisant » en utilisant .
I.G.2 Construire un automate qui reconnaît LS(M) à partir de la machine des
parties, en utilisant la propriété établie à la question I.G.1.
I.G.3 « Simplifier » l'automate construit avant d'en déterminer le langage.
I.H On peut détecter qu'un chemin passe par q0 dans une machine où q0 est un
état puits.
II.A Attention à la gestion des indices de début et de fin de file.
II.B Montrer qu'un sommet est inséré au plus une fois dans la file.
II.C La complexité de l'algorithme dépend du nombre de sommets insérés dans la
file et du nombre d'arcs parcourus.
II.D Montrer le résultat par récurrence sur le nombre de tours de boucle 
effectués.
II.E.1 Observer que quand l'algorithme change le contenu de D[s], cela provient 
de
la découverte d'un chemin de E à s d'une certaine longueur.
II.E.2 Raisonner par récurrence sur la valeur de ds . On pourra raisonner par 
l'absurde et obtenir une contradiction en utilisant le prédécesseur de s dans un
plus court chemin de E à s, ainsi que le sommet défilé juste avant l'insertion
de s dans la file.
II.G Utiliser la question II.E.2 pour construire le mot de longueur minimale de
façon récursive.
III.A Suivre la définition de la machine donnée au début de la partie. Dans une
telle machine, une transition depuis l'état qi,j correspond à la recherche de
la variable xj dans la clause i.
III.C Remarquer que les états accessibles à partir de qi,j en une transition 
sont
qi,j+1 (s'il existe) et f , puis généraliser cette remarque.
III.D Utiliser le lien entre l'appartenance d'un littéral dans une clause et 
les transitions de la machine.
III.E Raisonner comme à la question III.D. Penser à compléter le mot 
synchronisant de la machine pour obtenir une distribution de vérité totale.
IV.A.1 Montrer que cette suite est décroissante et calculer |Q.ur |.
IV.A.2 Pour l'implication réciproque, la propriété dit qu'on peut synchroniser 
deux
états quelconques. On peut chercher ensuite à synchroniser trois états, puis
formuler une récurrence pour synchroniser tous les états.
IV.C Les fonctions nb_to_set et set_to_nb permettent de passer entre les 
représentations de q par un entier et par un ensemble d'états.
e R.
IV.D Attention au nombre d'états du graphe retourné G
IV.E Reformuler la caractérisation de la question IV.A.2 en terme 
d'accessibilité
e R.
dans le graphe G
IV.F Implémenter la méthode proposée à la question IV.E.

I. Considérations générales
I.A Soit M une machine ayant un seul état, que l'on note q. Pour tout mot m de  
,
on a nécessairement q.m = q, donc m est un mot synchronisant. Par conséquent,
Tout mot est synchronisant pour une machine à un état.
Il faut bien comprendre qu'un mot m est synchronisant si, en partant de
n'importe quel état de la machine et en lisant m, on tombe toujours sur le
même état.
I.B Remarquons qu'une transition dans la machine M1 change la parité de l'état
courant. Pour tout m   , 1.m et 2.m ont alors des parités opposées. Or, si m est
un mot synchronisant, 1.m = 2.m, ce qui est impossible. Finalement,
M1 n'admet aucun mot synchronisant.
I.C Considérons le mot de trois lettres bcb. On a
1.bcb = 1.cb = 4.b = (4, b) = 4
2.bcb = 1.cb = 4
De même,

3.bcb = 4.cb = 3.b = (4, b) = 4
4.bcb = 4.cb = 4

ce qui prouve que

bcb est un mot synchronisant pour M2 .

I.D Pour implémenter la fonction delta_etoile, on suit la définition récursive
de   rappelée dans l'énoncé : si le mot est vide, on renvoie l'état en entrée, 
sinon on
fait une étape de calcul avec , et le reste du calcul est traité par appel 
récursif.
let rec delta_etoile machine etat mot = match mot with
| [] -> etat
| x::u -> delta_etoile machine (machine.delta etat x) u;;
I.E On utilise directement la définition d'un mot synchronisant : on veut 
vérifier,
étant donné un mot m, s'il existe un état q0 tel que pour tout état q, q.m = q0 
.
On trouve cet état q0 en partant d'un état quelconque de la machine, par 
exemple 0,
et en lisant m, soit q0 = 0.m. Il reste à vérifier la propriété pour tous les 
autres états
à l'aide d'une fonction récursive.
let est_synchronisant machine mot =
let etat_zero = delta_etoile machine 0 mot in
let rec verifie_etat machine mot etat =
if etat = 0 then true
else if (delta_etoile machine etat mot <> etat_zero) then false
else verifie_etat machine mot (etat-1)
in verifie_etat machine mot (machine.n_etats-1);;

On pourrait aussi utiliser une boucle while décroissante indicée par l'état à
vérifier à l'aide d'une référence. On utilise une autre référence pour détecter
si un état ne vérifie pas la propriété, auquel cas on peut sortir de la boucle
directement. La boucle while simule alors la fonction auxiliaire récursive
précédente.
let est_synchronisant_imperatif machine mot =
let etat_zero = delta_etoile machine 0 mot
and etat = ref (machine.n_etats-1)
and continue = ref true in
while (!continue && !etat > 0) do
if (delta_etoile machine !etat mot <> etat_zero)
then continue := false
else etat := !etat-1
done;
!continue;;
I.F Soit M une machine ayant un mot synchronisant u = u1 · · · un . Soient q0 
et q0
deux états de M distincts (c'est possible car M a au moins deux états). Notons
i  {1, . . . , n}

qi = q0 .(u1 · · · ui )

et

qi = q0 .(u1 · · · ui )

les états successivement rencontrés en lisant le mot u à partir des états q0 et 
q0
respectivement. Soit i le plus grand entier inférieur ou égal à n tel que qi 6= 
qi .
Comme u est synchronisant, qn = q0 .u = q0 .u = qn . De plus, q0 6= q0 . Ceci 
prouve
que i est bien défini. On pose enfin q = qi , q  = qi et x = ui+1 . Par 
définition q 6= q  ,

et q.x = qi .ui+1 = qi+1 = qi+1
= q  .x. Ainsi,
Une condition nécessaire d'existence d'un mot synchronisant est donnée par
x  

 q  Q  q  Q

q  6= q

et q.x = q  .x

De manière informelle, ce résultat dit que si une machine admet un mot
synchronisant, alors il existe une lettre qui synchronise deux états différents
de la machine. La question IV.A.2 montre un résultat similaire mais sous
forme de condition nécessaire et suffisante.
I.G.1 De la même manière que pour , on peut étendre la fonction de transition b 
en
b ×  , que l'on note b . M admet un mot synchronisant si et seuleune fonction 
de Q
ment s'il existe un mot u   et un état q0  Q tel que pour tout état q  Q, q.u = 
q0 ,
b b (Q, u) = {q0 }. Autrement dit,
ce qui équivaut à dire que, dans la machine M,
M admet un mot synchronisant si et seulement si il existe
b un état singleton {q0 } accessible depuis l'état Q.
dans M
Pour prouver qu'un langage est reconnaissable, une méthode générale
consiste à exhiber un automate fini qui reconnaît ce langage. Cette méthode 
semble particulièrement intéressante ici car la notion de machine est
très proche de celle d'automate.
b où I = Q
b , I, F, )
À une machine M, on associe l'automate déterministe AM = (Q,
est l'état initial de l'automate et F = {{q}, q  Q}, constitué des singletons, 
est l'ensemble des états finals de l'automate. Un mot u   est reconnu par 
l'automate AM
si et seulement si b (Q, u)  F, ce qui d'après la question I.G.1 revient à dire 
que u est
I.G.2