Concours blanc (MP option 2015-2016) — Automates synchronisables¶

Concours blanc · MP (option informatique) · 2015-2016 · 3 h

Cours : Automates finis déterministes · Modélisation par des automates · Parcours en largeur

Consignes

Tout document et instruments électroniques (calculatrices, téléphone portable, …) interdits.

Les automates finis ne permettent pas uniquement de reconnaître des langages : ce sont également de bons modèles des machines d'état permettant ainsi de modéliser des machines courantes.

Prenons l'exemple d'un distributeur de café ne rendant pas la monnaie. Celui-ci possède donc deux états :

état $I$ initial : aucun argent dans le distributeur ;
état $S$ : au moins une pièce dans le distributeur ;

et les interactions suivantes :

si on appuie sur le bouton $B$ dans l'état $I$ rien ne se passe et dans l'état $S$ tout l'argent est utilisé et le distributeur fait un café ;
si on place des sous dans le distributeur dans l'état $I$ on passe à l'état $S$ et si on était dans l'état $S$ on reste dans cet état.

Notons $b$ l'interaction appuyer sur le bouton et $a$ l'interaction insérer une pièce, on peut alors représenter le distributeur de café par l'automate fini suivant :

Notons que cet automate n'a pas d'état final car le distributeur marche en permanence.

Le problème qu'on se pose alors est celui du réparateur de distributeurs : sans connaître l'état du distributeur, existe-t-il un mot permettant de le mettre dans un état précis quel que soit son état ?

Ici, il existe plusieurs mots ayant cette propriété, on parle de mots de synchronisation, par exemple : $b$, $a$, $ab$ ou $ba$.

I. Définition des automates synchronisables¶

Dans tout le problème, on considère $\Sigma$ un alphabet contenant au moins deux lettres. On note $\mu$ le mot vide et $uv$ le mot constitué de la concaténation du mot $u$ et du mot $v$.

Soit $\mathcal{A} = (Q, \delta)$ un automate fini déterministe et complet, c'est-à-dire tel que :

$Q$ soit un ensemble fini non vide dont les éléments sont appelés les états de l'automate ;
et $\delta : Q \times \Sigma \rightarrow Q$ soit une application appelée la fonction de transition de $\mathcal{A}$.

On ne s'intéresse ni à l'état initial ni aux états finaux.

On note $\delta^*$ l'application prolongeant $\delta$ aux mots de $\Sigma^*$, c'est-à-dire telle que :

$\forall q \in Q, \delta^*(q, \mu) = q$ ;
$\forall a \in \Sigma, \forall m \in \Sigma^*, \forall q \in Q, \delta^*(q, a m) = \delta^*( \delta(q, a), m)$ ;

et ainsi on notera $\delta^*(Q, m) = \{\, \delta^*(q,m) \mid q \in Q \,\}$.

On pose $\Delta_m : q \mapsto \delta^*(q,m)$ et on rappelle que $\Delta_{uv} = \Delta_v \circ \Delta_u$.

Un mot $m \in \Sigma^*$ est appelé un mot de synchronisation de $\mathcal{A}$ ssi $\delta^*(Q,m)$ est un singleton, c'est-à-dire si $\Delta_m$ est une application constante.

On note $S(\mathcal{A})$ l'ensemble des mots de synchronisation de $\mathcal{A}$ ; quand cet ensemble est non vide on dit que $\mathcal{A}$ est un automate synchronisable.

Question 1

Déterminer $S(\mathcal{A}_1)$ où $\mathcal{A}_1$ est l'automate suivant :

Automate A1 — L'automate $\mathcal{A}_1$

Corrigé

N'importe quel mot contenant au moins une fois la lettre $b$ convient (lire $b$ envoie les deux états sur $0$), alors que $a$ est une bijection des états, donc $S(\mathcal{A}_1) = \Sigma^* \setminus \{a\}^*$.

Un mot $m \in \Sigma^*$ est appelé un mot régulier de $\mathcal{A}$ ssi $\Delta_m$ est bijective.

Question 2

Soit $\mathcal{A}$ un automate fini déterministe et complet sur $\Sigma$ ayant au moins deux états et $m \in \Sigma^*$ un mot de synchronisation de longueur minimale.

Justifier brièvement que $m$ ne peut être le mot vide puis montrer que $m$ ne peut avoir de préfixe ou de suffixe réguliers.

Corrigé

$\mathcal{A}$ ayant au moins deux états, $\delta^*(Q, \mu) = Q$ n'est pas un singleton : le mot vide n'est pas un mot de synchronisation.

Supposons que $m = uv$ avec $u$ régulier non vide. On a $\Delta_m = \Delta_v \circ \Delta_u$ donc $\Delta_v = \Delta_m \circ \Delta_u^{-1}$ est constante et $v$, plus petit que $m$, est un mot de synchronisation : contradiction. Idem pour les suffixes.

Question 3

Déterminer les mots réguliers de l'automate $\mathcal{A}_2$ suivant :

Automate A2 — L'automate $\mathcal{A}_2$

Corrigé

Les mots réguliers sont ceux de $\{a\}^*$ : $a$ est régulier, donc par composition $a^n$ est régulier. Et si $m = a^n b v$ est régulier alors $bv$ est régulier, mais $\delta^*(\{0,1,2\},bv) = \delta^*(\{0,1\},v)$ qui ne peut être égal à $\{0,1,2\}$, donc $bv$ n'est pas régulier.

Question 4

Montrer que l'automate $\mathcal{A}_2$ est synchronisable et déterminer le ou les mots de synchronisation de $\mathcal{A}_2$ de longueur minimale.

Corrigé

D'après les questions 2 et 3, un mot de synchronisation de longueur minimale de $\mathcal{A}_2$ ne peut ni commencer ni finir par $a$. On vérifie que $b$, $bb$, $bab$, $babb$ et $bbab$ ne sont pas des mots de synchronisation (et $bb$ agit comme $b$), mais $baab$ convient : $\{0,1,2\} \xrightarrow{b} \{0,1\} \xrightarrow{a} \{1,2\} \xrightarrow{a} \{0,2\} \xrightarrow{b} \{0\}$. C'est donc le mot de synchronisation de longueur minimale de $\mathcal{A}_2$.

Question 5

Montrer que pour tout automate fini déterministe et complet sur $\Sigma$ on a $S(\mathcal{A}) = \Sigma^* S(\mathcal{A}) \Sigma^*$.

Corrigé

L'inclusion $S(\mathcal{A}) \subset \Sigma^* S(\mathcal{A}) \Sigma^*$ est immédiate (avec $\mu$). Soit $m \in S(\mathcal{A})$ et $u, v \in \Sigma^*$ : on a $\delta^*(Q, umv) = \Delta_v(\Delta_m(\Delta_u(Q)))$ mais $\Delta_m(\Delta_u(Q)) \subset \Delta_m(Q) = \{q\}$, donc $\delta^*(Q, umv) = \{ \delta^*(q,v) \}$ et $umv$ est un mot de synchronisation.

II. Graphe d'automates¶

On va considérer ici le graphe associé à un automate fini déterministe et complet sur l'alphabet $\Sigma = \{ l_0, l_1, \cdots, l_m \}$.

Si $\mathcal{A} = (Q,\delta)$ est un tel automate, on définit $G_\mathcal{A} = (Q, A)$ le graphe de $\mathcal{A}$ où $A \subset Q \times Q \times \Sigma$ est l'ensemble des arêtes du graphe données sous la forme $(q_1, q_2, a)$ avec $q_1,q_2 \in Q$ et $a \in \Sigma$ quand il existe une transition telle que $q_2 = \delta(q_1, a)$ dans l'automate.

Attention, il ne s'agit pas d'un graphe simple car il peut y avoir des boucles, i.e. des arêtes partant d'un sommet et arrivant sur lui-même, et des arêtes parallèles, i.e. des arêtes ayant même source et même but ; elles sont alors forcément différenciées par la lettre de $\Sigma$ qui leur est associée.

Pour représenter en OCaml un tel graphe, on peut s'appuyer sur le fait que l'automate est complet. On considère que $Q = \{ 0, 1, 2, \cdots, n\}$ et on représente $G_\mathcal{A}$ par une matrice $A = \left( \delta(i,l_j) \right)_{0 \le i \le n,\ 0 \le j \le m}$.

Donc par le type OCaml :

type graphe = int array array

En posant $l_0= a$ et $l_1 = b$, le graphe de l'automate $\mathcal{A}_1$ est donné par l'expression OCaml suivante :

let g1 = [| [| 1; 0 |]; [| 0; 0 |] |]

Question 6

Donner l'expression du graphe de l'automate $\mathcal{A}_2$ de la partie précédente.

Corrigé

let g2 = [| [| 1; 0 |]; [| 2; 1 |]; [| 0; 0 |] |]

Question 7

Écrire une fonction OCaml de signature delta : graphe -> int -> int -> int telle que l'appel à delta g i j renvoie la valeur de $\delta(i, l_j)$ où $\delta$ est la fonction de transition associée à l'automate de graphe $g$.

Corrigé

let delta g i j = g.(i).(j)

Question 8

Écrire une fonction OCaml de signature delta_etoile : graphe -> int -> int list -> int telle que l'appel à delta_etoile g i m renvoie la valeur de $\delta^*(i, m)$ où $\delta^*$ est le prolongement à $\Sigma^*$ de la fonction de transition associée à l'automate de graphe $g$ et où $m$ est représenté par la liste des indices de ses lettres (ex : $l_2 l_1 l_2 l_0 \rightarrow$ [2; 1; 2; 0]).

Corrigé

let rec delta_etoile g i m =
  match m with
  | [] -> i
  | t :: q -> delta_etoile g (delta g i t) q

Question 9

Écrire une fonction OCaml de signature appartient : 'a -> 'a list -> bool telle que l'appel à appartient x l renvoie le booléen true si et seulement si $x$ est présent dans la liste $l$.

Corrigé

let rec appartient x l =
  match l with
  | [] -> false
  | t :: q -> x = t || appartient x q

Question 10

Écrire une fonction OCaml de signature ajoute : 'a -> 'a list -> 'a list telle que l'appel à ajoute x l où $l$ est une liste sans répétitions renvoie une liste sans répétitions contenant tous les éléments de $l$ ainsi que $x$.

Corrigé

let ajoute x l = if appartient x l then l else x :: l

Question 11

Écrire une fonction OCaml de signature applique_mot : graphe -> int list -> int list telle que l'appel à applique_mot g m renvoie $\delta^*(Q,m)$ sous forme de liste sans répétitions où $\delta^*$ est définie comme à la question précédente et où $Q$ est l'ensemble des états de l'automate associé à $g$.

Exemple : applique_mot g1 [0] $\rightarrow$ [0; 1] (à l'ordre près).

Corrigé

let applique_mot g m =
  let n = Array.length g in
  let rec iteri k =
    if k >= n then []
    else ajoute (delta_etoile g k m) (iteri (k + 1))
  in
  iteri 0

Question 12

En déduire une fonction OCaml de signature synchronisant : graphe -> int list -> bool telle que l'appel à synchronisant g m renvoie un booléen indiquant si $m$ est un mot de synchronisation de l'automate associé à $g$.

Corrigé

let synchronisant g m = List.length (applique_mot g m) = 1

III. Automate des parties¶

Soit $\mathcal{A} = (Q, \delta)$ un automate fini non nécessairement déterministe ou complet ; on note $\mathcal{P}(\mathcal{A}) = (\mathcal{P}(Q), \delta')$ l'automate des parties de $\mathcal{A}$ défini par la fonction de transition :

\[ \forall E \subset Q, \forall a \in \Sigma, \delta'(E, a) = \{\, \delta(q,a) \mid q \in E \,\} \]

Par construction, l'automate $\mathcal{P}(\mathcal{A})$ est déterministe et complet.

L'automate $\mathcal{P}(\mathcal{A}_1)$, où $\mathcal{A}_1$ est un des exemples de la première partie, est donné par :

Automate des parties de A1 — L'automate des parties $\mathcal{P}(\mathcal{A}_1)$

Question 13

Déterminer $\mathcal{P}(\mathcal{A}_2)$ où $\mathcal{A}_2$ est un des exemples de la première partie.

Soit $Q = \{ 0, 1, \cdots, n\}$ et $E = \{i_1, \cdots, i_m\} \subset Q$ une partie à $m$ éléments, on pose $\mathsf{code}(E) = \sum_{k=1}^m 2^{i_k}$.

Question 14

Écrire une fonction OCaml de signature puissance2 : int -> int telle que l'appel à puissance2 n renvoie $2^n$.

Corrigé

let rec puissance2 n =
  match n with
  | 0 -> 1
  | _ -> 2 * puissance2 (n - 1)

Question 15

Écrire une fonction OCaml de signature code : int list -> int telle que l'appel à code e renvoie la valeur $\mathsf{code}(E)$ où $E$ est donné comme une liste sans répétition de ses éléments.

Corrigé

let rec code l =
  match l with
  | [] -> 0
  | t :: q -> puissance2 t + code q

Question 16

Écrire une fonction OCaml de signature decode : int -> int list telle que decode (code e) = e et code (decode n) = n.

On demande ainsi que decode n renvoie la liste sans répétitions d'états représentant $E$ où $\mathsf{code}(E) = n$.

Corrigé

let decode n =
  let rec aux n i =
    if n = 0 then []
    else if n mod 2 = 1 then i :: aux (n / 2) (i + 1)
    else aux (n / 2) (i + 1)
  in
  aux n 0

On va considérer ici une énumération de l'alphabet $\Sigma = \{ l_0, l_1, \cdots, l_m \}$ comme dans la partie précédente.

En reprenant la définition des graphes d'automates vue à la partie précédente et en identifiant $E \subset Q$ à l'entier $\mathsf{code}(E)$, on peut définir le graphe d'un automate des parties et en déduire sa représentation en OCaml. L'automate $\mathcal{P}(\mathcal{A}_1)$ est alors représenté par :

let pg1 = [| [| 0; 0 |]; (* partie vide, code 0 *)
             [| 2; 1 |]; (* partie { 0 }, code 1 *)
             [| 1; 1 |]; (* partie { 1 }, code 2 *)
             [| 3; 1 |]  (* partie { 0, 1 }, code 3 *) |]

Question 17

Écrire une fonction OCaml de signature transition_parties : graphe -> int list -> int -> int list telle que l'appel à transition_parties g e j où $e$ est une liste sans répétitions d'états renvoie $\delta'(E, l_j)$ représenté par une liste sans répétitions d'états.

Corrigé

let rec transition_parties g l j =
  match l with
  | [] -> []
  | t :: q -> ajoute (delta g t j) (transition_parties g q j)

Question 18

Écrire une fonction OCaml de signature automate_parties : graphe -> graphe telle que l'appel à automate_parties g renvoie la représentation du graphe d'automate de $\mathcal{P}(\mathcal{A})$ où $\mathcal{A}$ est représenté par le graphe d'automate $g$.

Corrigé

let automate_parties g =
  let n = Array.length g in
  let sigma = Array.length g.(0) in
  let np = puissance2 n in
  let gp = Array.make_matrix np sigma 0 in
  for i = 0 to np - 1 do
    let l = decode i in
    for j = 0 to sigma - 1 do
      gp.(i).(j) <- code (transition_parties g l j)
    done
  done;
  gp

On vérifie que automate_parties g1 est bien égal à pg1.

Question 19

Donner une caractérisation simple en terme de graphe du fait qu'une lettre de $\Sigma$ soit un mot régulier de $\mathcal{A}$.

Corrigé

La lettre $a$ est régulière si et seulement s'il n'existe pas deux arêtes d'étiquette $a$ arrivant sur un même sommet, autrement dit si chaque sommet est le but d'exactement une arête d'étiquette $a$.

Question 20

Montrer que $\mathcal{A} = (Q,\delta)$ est synchronisable si et seulement s'il existe un chemin dans le graphe associé à $\mathcal{P}(\mathcal{A})$ depuis le sommet $Q$ vers un singleton.

Indication : on pourra faire un lien explicite entre un mot de synchronisation de $\mathcal{A}$ et un tel chemin.

Corrigé

Par récurrence sur la longueur de $m$, le chemin d'étiquette $m$ partant de $Q$ dans $\mathcal{P}(\mathcal{A})$ aboutit en $\delta^*(Q,m)$. L'étiquette d'un chemin de $Q$ vers un singleton est donc toujours un mot de synchronisation et, réciproquement, en suivant l'unique chemin d'étiquette un mot de synchronisation à partir de $Q$ on est certain d'arriver sur un singleton.

Question 21

En supposant que $\mathcal{A}$ est synchronisable, en déduire un majorant sur la longueur d'un mot de synchronisation de longueur minimale.

Corrigé

Un chemin de longueur minimale ne passe pas deux fois par le même sommet, sa longueur ne peut donc dépasser le nombre de sommets moins un, c'est-à-dire $2^{|Q|}-1$, ce qui est ainsi un bon majorant.

Comme l'ensemble vide est toujours isolé, on peut même se ramener à $2^{|Q|}-2$.

IV. Parcours en largeur de l'automate des parties¶

À l'aide de la dernière question on en déduit un algorithme permettant de déterminer un mot de synchronisation de taille minimale pour un automate synchronisable. On va implémenter cet algorithme à l'aide d'un parcours en largeur.

Pour cela on se donne une structure de données abstraite 'a paquet munie de l'interface suivante :

val creer : unit -> 'a paquet (* crée un paquet vide *)
val est_vide : 'a paquet -> bool (* teste si le paquet est vide *)

val ajoute_elt : 'a paquet -> 'a -> unit (* ajoute un élément au paquet *)

val retire_ancien : 'a paquet -> 'a (* renvoie la valeur de l'élément *)
              (* ajouté le plus anciennement et le retire du paquet *)

val retire_recent : 'a paquet -> 'a (* renvoie la valeur de l'élément *)
              (* ajouté le plus récemment et le retire du paquet *)

Question 22

Soit $G = (S,A)$ un graphe et $x_0 \in S$.

Rappeler le principe d'un parcours en largeur de $G$ à partir du sommet $x_0$ avec du pseudo-code informel utilisant la structure de données paquet.

On pourra matérialiser l'état actuel du parcours par un tableau tri-valué indexé par $S$, où à chaque sommet on associe un état Visité, Découvert et Inconnu.

Corrigé

On part du sommet initial, on maintient une file (paquet utilisé avec retire_ancien) de sommets à visiter contenant au départ le sommet initial et on marque tous les sommets comme étant inconnus.

Tant que la file est non vide, on enlève un sommet, on le marque comme étant visité et on ajoute tous ses voisins inconnus dans la file ; on les passe alors à l'état découvert pour qu'ils ne soient pas à nouveau ajoutés.

Étant donné un parcours d'un graphe d'automate $G = (Q,A)$, on pose, pour $x \in Q$ visité par le parcours et différent du sommet initial, $\mathsf{pred}(x) = (y,a)$ où $y$ est le sommet à partir duquel on a découvert $x$ (c'est-à-dire celui pour lequel l'état de $x$ est passé de I à D) et où $a \in \Sigma$ est l'étiquette de l'arête empruntée pour aller de $y$ vers $x$. Quand il y a plusieurs lettres possibles, on choisira celle d'indice minimal.

Question 23

Détailler un parcours en largeur du graphe d'automate de $\mathcal{P}(\mathcal{A}_1)$ tel qu'il est donné dans la partie précédente à partir de l'élément $\{0,1\}$.

On décrira notamment complètement l'application $\mathsf{pred}$.

Question 24

Écrire une fonction OCaml de signature parcours_largeur : graphe -> int -> (int * int) array telle que l'appel à parcours_largeur g x renvoie le tableau $\mathsf{pred}$ déduit du parcours en largeur de $g$ à partir du sommet $x$.

Quand un sommet n'a pas de valeur associée par $\mathsf{pred}$, on posera $\mathsf{pred}(x) = (-1,-1)$.

On pourra considérer défini le type somme type etat = Inconnu | Decouvert | Visite.

Corrigé

let creer () = Queue.create ()
let est_vide p = Queue.is_empty p
let ajoute_elt p x = Queue.add x p
let retire_ancien p = Queue.take p

type etat = Inconnu | Decouvert | Visite

let parcours_largeur g x0 =
  let n = Array.length g in
  let sigma = Array.length g.(0) in
  let etats = Array.make n Inconnu in
  let pred = Array.make n (-1, -1) in
  let a_visiter = creer () in
  ajoute_elt a_visiter x0;
  while not (est_vide a_visiter) do
    let x = retire_ancien a_visiter in
    etats.(x) <- Visite;
    for j = 0 to sigma - 1 do
      let y = g.(x).(j) in
      if etats.(y) = Inconnu then begin
        etats.(y) <- Decouvert;
        pred.(y) <- (x, j);
        ajoute_elt a_visiter y
      end
    done
  done;
  pred

Question 25

Écrire une fonction OCaml de signature mot_chemin : (int * int) array -> int -> int list telle que l'appel à mot_chemin pred x renvoie le mot, sous forme de liste de lettres, du chemin déduit du parcours en largeur représenté par $\mathsf{pred}$ vers le sommet $x$.

Corrigé

On remonte de $x$ vers le sommet initial en ajoutant les lettres en tête d'un accumulateur, ce qui les remet dans l'ordre du chemin :

let mot_chemin pred x =
  let rec aux x acc =
    if pred.(x) = (-1, -1) then acc
    else let y, a = pred.(x) in aux y (a :: acc)
  in
  aux x []

Question 26

En déduire une fonction OCaml de signature mot_de_synchronisation_minimal : graphe -> int list telle que l'appel à mot_de_synchronisation_minimal g renvoie un mot de synchronisation minimal de l'automate représenté par $g$ supposé synchronisable.

Corrigé

On fait un parcours en largeur de $\mathcal{P}(\mathcal{A})$ depuis $Q$, de code $2^n - 1$, puis on garde le plus court des chemins menant à un singleton $\{i\}$, de code $2^i$ (le cas $n = 1$, où $Q$ est lui-même un singleton, donne le mot vide) :

let mot_de_synchronisation_minimal g =
  let n = Array.length g in
  let gp = automate_parties g in
  let tout = puissance2 n - 1 in
  let pred = parcours_largeur gp tout in
  let meilleur = ref None in
  for i = 0 to n - 1 do
    let s = puissance2 i in
    if pred.(s) <> (-1, -1) || s = tout then begin
      let m = mot_chemin pred s in
      match !meilleur with
      | Some m' when List.length m' <= List.length m -> ()
      | _ -> meilleur := Some m
    end
  done;
  match !meilleur with
  | Some m -> m
  | None -> failwith "automate non synchronisable"

Sur l'automate $\mathcal{A}_2$, mot_de_synchronisation_minimal g2 renvoie [1; 0; 0; 1], c'est-à-dire $baab$.

Question 27

Quelle est la complexité totale de la fonction mot_de_synchronisation_minimal en fonction du nombre d'états ?

On pourra considérer connue la complexité d'un parcours en largeur en supposant que les opérations sur la structure paquet sont en $\mathcal{O}(1)$.

Corrigé

Notons $n = |Q|$ et $p = |\Sigma|$. Le graphe de l'automate des parties a $2^n$ sommets, chacun de degré sortant $p$, donc $p\,2^n$ arêtes.

Construction de l'automate des parties : pour chacune des $p\,2^n$ transitions, decode est en $\mathcal{O}(n)$, transition_parties en $\mathcal{O}(n^2)$ (chaque ajoute est linéaire) et code en $\mathcal{O}(n^2)$ (à cause de puissance2), soit $\mathcal{O}(p\, n^2\, 2^n)$.
Parcours en largeur : $\mathcal{O}(2^n + p\,2^n) = \mathcal{O}(p\,2^n)$.
Reconstruction des mots : chacun des $n$ chemins est de longueur au plus $2^n$ (question 21), soit $\mathcal{O}(n\,2^n)$.

La complexité totale est donc en $\mathcal{O}(p\, n^2\, 2^n)$ : exponentielle en le nombre d'états.

V. Reconnaissance des automates synchronisables¶

Dans cette partie on note $|E|$ le nombre d'éléments de l'ensemble $E$.

Soit $\mathcal{A} = (Q, \delta)$ un automate sur l'alphabet $\Sigma$ et $m \in \Sigma^*$. On pose $\rho(m) = \left|\delta^*(Q, m)\right|$ le nombre d'états atteints en suivant le mot $m$ à partir de chaque état.

Avec ces notations, $m$ est un mot de synchronisation si et seulement si $\rho(m) = 1$.

On considère la propriété $(\star)$ sur les automates :

\[ (\star) : \forall q,q' \in Q, \exists m \in \Sigma^*, \delta^*(q,m) = \delta^*(q',m) \]

Question 28

Soit $\mathcal{A}$ un automate vérifiant la propriété $(\star)$ et $m \in \Sigma^*$ tel que $|Q| > \rho(m) > 1$.

Montrer qu'il existe $m'$ tel que $\rho(mm') < \rho(m)$.

Corrigé

Comme $\rho(m) > 1$, soient $q \neq q'$ dans $\delta^*(Q,m)$ et, par $(\star)$, $m'$ tel que $\delta^*(q,m') = \delta^*(q',m')$. On a $\delta^*(Q, mm') = \Delta_{m'}(\delta^*(Q,m))$ où $q$ et $q'$ ont la même image : cet ensemble contient au moins un état de moins que $\delta^*(Q,m)$, et ainsi $\rho(mm') < \rho(m)$.

Question 29

En déduire que $\mathcal{A}$ est un automate synchronisable si et seulement s'il vérifie la propriété $(\star)$.

Corrigé

Supposons que $\mathcal{A}$ ne soit pas synchronisable mais vérifie $(\star)$, et soit $m$ un mot tel que $\rho(m)$ soit minimal. On a forcément $|Q| > \rho(m) > 1$ car d'une part il existe des mots non réguliers par $(\star)$ et d'autre part $m$ n'est pas de synchronisation donc $\rho(m) \neq 1$. Ainsi la question 28 s'applique et il existe $m'$ tel que $\rho(mm') < \rho(m)$. Contradiction avec la minimalité.

Question 30

Soit $\mathcal{A}$ un automate déterministe. Justifier que pour toute transition $A \xrightarrow{a} B$ dans son automate des parties on a $|A| \ge |B|$.

Corrigé

Pour chaque état de $A$, on ne peut atteindre qu'un état par $a$ vu que l'automate est déterministe, donc l'ensemble $B$ des états accessibles en lisant $a$ depuis $A$ ne peut contenir strictement plus d'états que $A$.

Question 31

En déduire un algorithme de complexité polynomiale en temps ET en espace pour reconnaître les automates synchronisables.

On donnera explicitement la complexité de l'algorithme.

Corrigé

Par la question 29, il suffit de vérifier $(\star)$, c'est-à-dire l'existence pour toute paire $\{q,q'\}$ d'un chemin vers un singleton dans l'automate des parties. Par la question 30, un tel chemin ne passe que par des états à au plus 2 éléments : on se restreint donc à la partie de l'automate des parties formée des parties à un ou deux éléments.

Cette accessibilité d'un singleton depuis $\{q,q'\}$ peut se résoudre par parcours ; la complexité dépend donc du nombre de sommets, c'est-à-dire du nombre de parties à au plus 2 éléments, $n + n(n-1)/2$.

Il existe de très nombreuses applications des mots de synchronisation. Citons-en deux :

L'équipe d'Ehud Shapiro a réalisé en 2001 une soupe d'automates avec des brins d'ADN dans un tube à essai. En fournissant d'autres brins les automates calculent tous en parallèle et ils finissent ainsi dans des états différents où il est impossible de les changer un par un. Ils ont donc utilisé une solution composée de mots de synchronisation pour les réinitialiser.
En ingénierie il est courant d'usiner une pièce et qu'elle se retrouve sur une chaîne de transport dans une orientation aléatoire. Afin de procéder à l'assemblage il est nécessaire de déterminer une suite de transformations géométriques à opérer pour placer la pièce dans une orientation fixe. Il s'agit là de chercher un mot de synchronisation dans l'automate où les états sont les orientations et les transitions sont données par les différentes transformations géométriques.