Centrale Informatique optionnelle MP 2017

î. '» 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