L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Automates et matrices pondérés
Ce sujet comporte six pages et quatre parties. Il porte sur l'étude d'automates pondérés, de leur modélisation mathématique et de certains de leurs comportements asymptotiques.
La partie I introduit la notion d'automate pondéré, de langage pondéré (à chaque mot est associé un poids) et établit leurs premières propriétés. La partie II s'intéresse au poids d'un mot choisi aléatoirement. La partie III fait le lien entre un automate et sa représentation matricielle, et enfin, la partie IV s'intéresse au comportement asymptotique des automates et des matrices pondérés.
Les notions introduites en partie I sont utilisées dans les parties II et III. La partie IV s'appuie sur certains résultats de la partie III. Les résultats d'une question pourront être admis dans la suite du sujet.
Partie I. Automates pondérés
On appelle automate pondéré un automate fini dont les arêtes ont un poids. Plus précisément, c'est un sextuplet A = (Q, Σ, I, F, E, W), où
Q est l'ensemble fini des états;
Σ est un alphabet fini;
I, F ⊆ Q sont respectivement les états initiaux et terminaux de l'automate;
E ⊆ Q × Σ × Q sont les transitions de l'automate;
W : E → ℝ est la fonction de pondération qui à chaque transition associe un nombre réel.
Un chemin dans l'automate A est une suite finie de transitions s = (e_1, e_2, …, e_k) avec k ∈ ℕ, e_i = (p_i, a_i, q_i) ∈ E et tels que ∀i ∈ {1…, k − 1}, q_i = p_(i + 1). Ce chemin est un cycle si p_1 = q_k et c'est un cycle élémentaire s'il n'existe pas 1 ≤ i < j ≤ k tel que p_i = p_j. Enfin, ce chemin est sans cycle s'il n'existe pas 1 ≤ i ≤ j ≤ k tel que ( e_i, …, e_j ) est un cycle.
L'entier k est la longueur de ce chemin; le mot u = a_1…a_k est le mot (ou étiquette) de ce chemin; et le poids de ce chemin est
W(s) = ∑_(i = 1)^k W(e_i), avec la convention ∑_(i = 1)^0 W(e_i) = 0
Ce chemin est dit acceptant si q_1 ∈ I et q_k ∈ F. Si un mot u ∈ Σ^∗ est accepté par l'automate s'il existe un chemin acceptant de mot u. Le poids T_A(u) d'un mot u dans l'automate est le poids maximal d'un chemin acceptant de mot u. Si un tel chemin n'existe pas, alors par convention, le poids du mot est − ∞ :
T_A(u) = max{W(s)|s chemin acceptant de mot u dans A}
Un langage pondéré L sur un alphabet fini Σ^∗ est un ensemble tel qu'il existe w : Σ^∗ → ℝ ∪ { − ∞} tel que L = {(u, w(u))|u ∈ Σ^∗}. Le poids de u ∈ Σ^∗ dans L est L(u) = w(u), et on note Supp(L) = {u ∈ Σ^∗|L(u) ≠ − ∞} le support du langage.
Le langage L_A = {(u, T_A(u))|u ∈ Σ^∗} est le langage pondéré reconnu par l'automate : pour tout mot u ∈ Σ^∗, L_A(u) = T_A(u).
On supposera dans tout le problème que tous les états des automates pondérés sont utiles : pour tout état q ∈ Q, il existe i ∈ I et f ∈ F tels qu'il existe un chemin de i à q et un chemin de q à f.
Question 1
a. Montrer que le support du langage d'un automate pondéré est un langage reconnu par un automate fini.
b. Réciproquement, montrer que si L est un langage reconnu par un automate fini, il est possible de trouver un automate pondéré A de support L tel que u ∈ L ⇔ L_A(u) = 0.
Question 2 On pose Σ = {a, b}.
a. Quel est le langage pondéré sur Σ^∗ reconnu par l'automate pondéré suivant? La notation " a|w "signifie que la transition est étiquetée par a et de poids w. Les flèches entrantes désignent les états initiaux et les flèches sortantes les états terminaux.
b. Donner un automate pondéré sur Σ^∗ reconnaissant le langage {(u, max(|u|_a, |u|_b)), u ∈ Σ^∗}, où |u|_a (respectivement |u|_b ) est le nombre d'occurrences de a (respectivement b ) dans u.
On fixe c ∈ ℝ. On s'intéresse au problème de savoir si tous les poids des mots reconnus par un automate pondéré sont inférieurs à c.
On note L le langage pondéré reconnu par l'automate pondéré A.
Question 3
a. Montrer que pour tout mot u, L(u) ≤ c si et seulement si tous les chemins acceptants de A d'étiquette u sont de poids inférieur ou égal à c.
b. Montrer que l'on a l'équivalence entre les deux assertions :
(i) ∀u ∈ Σ^∗, L(u) ≤ c.
(ii) tous les cycles élémentaires de l'automate pondéré sont négatifs ou nuls et tous les chemins acceptants sans cycle sont de poids inférieur ou égal à c.
Partie II. Poids asymptotique d'un mot choisi aléatoirement
Dans cette partie on s'intéresse aux deux automates A_1 et A_2 suivants, où h_a, h_b ∈ ℕ.
Soient Σ = {a, b} et k ∈ ℕ∖{0}. Considérons l'espace probabilisé ( Σ^k, P(Σ^k), P ) tel que pour tout i ∈ {0, …, k − 1}, P(Σ^i aΣ^(k − i − 1)) = p et P(Σ^i bΣ^(k − i − 1)) = 1 − p = q et tel que les événements E_i = Σ^i aΣ^(k − i − 1) forment une famille mutuellement indépendante. Si X est une variable aléatoire sur ℕ, on note E[X] son espérance et Var(X) sa variance.
Question 4 Soit u ∈ Σ^k. Calculer P(u).
Soit X_k une variable aléatoire sur Σ^k.
Question 5 On s'intéresse dans cette question à l'automate A_1. On pose α = max(ph_a, qh_b).
a. Calculer E[|X_k|_a] et Var(|X_k|_a). (On rappelle que |X_k|_a est le nombre d'occurrences de a dans X_k.)
b. Montrer que pour tout β > p, il existe δ_1 > 0 tel que P(|X_k|_a ≥ βk) ≤ (δ_1)/k et que pour tout γ < p, il existe δ_2 > 0 tel que P(|X_k|_a ≤ γk) ≤ (δ_2)/k.
c. Quel est le langage pondéré reconnu par l'automate A_1 ?
d. Déduire des questions précédentes que lim_(k → ∞)(E[L_(A_1)(X_k)])/k = α (Indication : on pourra d'abord montrer que pour tout ε > 0, il existe δ > 0 tel que P(|L_(A_1)(X_k) − αk| ≥ εk) ≤ δ/k).
Question 6 On s'intéresse maintenant à l'automate A_2. On note Y_i l'état obtenu après lecture du mot X[i], le préfixe de X_k de longueur i, (ici, on a donc Y_0 = 2 ).
a. Pour tout i ∈ {1, …, k}, calculer P(Y_i = 1).
b. En déduire P(Y_i = 2) et P(Y_i = 3).
c. En déduire lim_(k → ∞)(E[L_(A_2)(X_k)])/k. (Indication : on pourra s'intéresser à E[L_(A_2)(X[i]) − L_(A_2)(X[i − 1])] ).
Partie III. Matrices pondérées
Soit ℝ^– = ℝ ∪ { − ∞}. On appelle matrice pondérée une matrice à coefficients dans ℝ^–. Soient B, C ∈ ℝ^–^(n, n) deux matrices pondérées. On définit les opérations suivantes : − B ⊕ C par ∀i, j ∈ {1, …, n}, (B ⊕ C)_(i, j) = max(B_(i, j), C_(i, j));
B ⊗ C par ∀i, j ∈ {1, …, n}, (B ⊗ C)_(i, j) = max_(k ∈ {1, …, n})(B_(i, k) + C_(k, j)).
Un vecteur pondéré est un élément de ℝ^–^(1, n) (vecteur ligne) ou ℝ^–^(n, 1) (vecteur colonne). On définit de la même manière
pour B ∈ ℝ^–^(n, n) et u ∈ ℝ^–^(n, 1), B ⊗ upar∀i ∈ {1, …, n}, (B ⊗ u)_i = max_(j ∈ {1, …, n})(B_(i, j) + u_j);
pour B ∈ ℝ^–^(n, n) et u ∈ ℝ^–^(1, n), u ⊗ B par ∀i ∈ {1, …, n}, (u ⊗ B)_i = max_(j ∈ {1, …, n})(u_j + B_(j, i)).
Question 7
a. Montrer que l'opération ⊕ est associative : pour tous B, C, D ∈ ℝ^–^(n, n), (B ⊕ C) ⊕ D = B ⊕ (C ⊕ D).
b. Montrer que l'opération ⊕ est commutative : pour tous B, C ∈ ℝ^–^(n, n), B ⊕ C = C ⊕ B.
c. Montrer que l'opération ⊗ est associative : pour tous B, C, D ∈ ℝ^–^(n, n), (B ⊗ C) ⊗ D = B ⊗ (C ⊗ D).
d. Montrer que l'opération ⊗ est distributive sur ⊕ : B, C, D ∈ ℝ^–^(n, n), B ⊗ (C ⊕ D) = (B ⊗ C) ⊕ (B ⊗ D) et (C ⊕ D) ⊗ B = (C ⊗ B) ⊕ (D ⊗ B).
e. Donner une matrice U ∈ ℝ^–^(n, n) telle que pour tout B ∈ ℝ^–^(n, n), B ⊗ U = U ⊗ B = B.
Soit M ∈ ℝ^–^(n, n). On pose M^0 = U et pour tout k ∈ ℕ, M^(k + 1) = M ⊗ M^k.
Une matrice M ∈ ℝ^–^(n, n) peut être représentée par un graphe orienté et pondéré G(M) = ( S, A, w ) dont l'ensemble des sommets est S = {1, …, n}, l'ensemble des arcs est A = {(i, j)|M_(i, j) ≠ − ∞}, et la fonction de pondération est w : A → ℝ; (i, j) ↦ M_(i, j).
Question 8 Montrer que (M^k)_(i, j) est égal au poids maximal d'un chemin de longueur k de i vers j dans G(M) (on utilisera la convention qu'un chemin de longueur 0 est de poids nul et que s'il n'y a pas de chemin de i vers j de longueur k, ce poids est − ∞ ).
Soit A = (Q, Σ, I, F, E, W) un automate pondéré avec Q = {1, …, n}. Pour tout a ∈ Σ, soit M(a) la matrice du graphe pondéré obtenu en ne gardant que les transitions d'étiquette a : G(M(a)) = (Q, A, w), avec A = {(p, q)|(p, a, q) ∈ E} et w : (p, q) ↦ W(p, a, q). Pour tout u = a_1…a_k ∈ Σ^∗, on pose M(u) = M(a_1) ⊗ ⋯ ⊗ M(a_k) avec la convention M(u) = U si u est le mot vide.
Question 9
a. Soient p, q ∈ Q. Montrer que le poids maximum d'un chemin d'étiquette u ∈ Σ^∗ de p vers q est égal à M(u)_(p, q).
b. En déduire une expression matricielle pour L_A(u), c'est-à-dire de la forme M_1 ⊗ ⋯ ⊗ M_ℓ où M_i sont des matrices ou des vecteurs.
On suppose dans la question suivante que tous les cycles dans l'automate sont de poids négatif ou nul.
Question 10
a. Considérons la matrice M = ⊕ _(a ∈ Σ)M(a) et M^∗ = ⊕ _(k ∈ ℕ)M^k. Montrer que M^∗ est bien définie (c'est-à-dire que ses coefficients sont dans ℝ^– ).
b. Donner une expression matricielle pour le poids du mot le plus lourd reconnu par l'automate A.
c. Soit M_(i, j)^(≤ p) le poids maximal d'un chemin de i vers j passant uniquement par des sommets intermédiaires q tels que q ≤ p ( i et j non compris). On pose M^(≤ p) = (M_(i, j)^(≤ p))_(i, j ≤ n). Exprimer M_(i, j)^(≤ p) en fonction de M^(≤ p − 1). En déduire un algorithme par programmation dynamique qui calcule M^∗.
d. Adapter cet algorithme pour qu'il réponde vrai si tous les mots reconnus par l'automate sont de poids inférieur ou égal à c et faux sinon, sans faire d'hypothèse a priori sur les poids des cycles de l'automate.
Partie IV. Croissance asymptotique du poids des mots
On dit qu'une matrice pondérée est irréductible si le graphe orienté qui lui est associé est fortement connexe. Soit M une matrice pondérée irréductible. On suppose dans les questions 11 à 14 que le cycle de poids maximum dans ce graphe est de poids exactement égal à zéro.
On appelle vecteur propre de M associé à la valeur propre λ ∈ ℝ un vecteur v ≠ (− ∞, …, − ∞) tel que M ⊗ v = λ ⊗ v, où λ ⊗ v est le vecteur (λ + v_1, …, λ + v_n).
Soient v, v^′ ∈ ℝ^–^(n, 1). On note v ≤ v^′ si pour tout i ∈ {1, …, n}, v_i ≤ v_i^′ et de la même manière, on note v ≥ v^′ si pour tout i ∈ {1, …, n}, v_i ≥ v_i^′.
Question 11 Soient v ≠ (− ∞, …, − ∞) et λ ∈ ℝ tels que M ⊗ v ≤ λ ⊗ v.
a. Montrer que pour tout k ∈ ℕ, M^k ⊗ v ≤ (kλ) ⊗ v puis que ∀i ∈ {1, …, n}, v_i ≠ − ∞.
b. En déduire que λ ≥ 0.
Question 12 Soient v ≠ (− ∞, …, − ∞) et λ ∈ ℝ tels que M ⊗ v ≥ λ ⊗ v.
a. Montrer que pour tout i ∈ {1, …, n} il existe j ∈ {1, …, n} tel que λ + v_i ≤ M_(i, j) + v_j.
b. En déduire que λ ≤ 0.
Soit I^∗ l'ensemble des sommets de G(M) qui sont sur un cycle de poids 0 .
Question 13 Montrer que pour i ∈ I^∗, le i-ème vecteur colonne de M^∗ est un vecteur propre pour M. Quel est l'ensemble des valeurs propres de M ?
Pour i, j ∈ {1, …, n} et i^∗ ∈ I^∗, on note (M^k)_(i, i^∗, j) = max_(k_1 + k_2 = k)(M^(k_1))_(i, i^∗) + (M^(k_2))_(i^∗, j) le poids du chemin le plus lourd de i vers j de longueur k et passant par i^∗.
Question 14
a. Montrer qu'il existe d ∈ ℕ∖{0} tel que pour tout i^∗ ∈ I^∗, (M^d)_(i^∗, i^∗) = 0.
b. Soient i, j ∈ {1, …, n} et i^∗ ∈ I^∗. Montrer qu'il existe K > 0 tel que pour tout k ≥ K, (M^((k + 1)d))_(i, i^∗, j) = (M^(kd))_(i, i^∗, j).
c. Soient i, j ∈ {1, …, n}. Montrer qu'il existe K^′ tel que pour tout k ≥ K^′, M_(i, j)^(kd) = max_(i^∗ ∈ I^∗)(M^(kd))_(i, i^∗, j).
d. En déduire qu'il existe K_0 et d tels que pour tout k ≥ K_0, M^(k + d) = M^k.
On se place maintenant dans le cas où le cycle de poids maximal n'est plus égal à 0 , mais la matrice M est toujours irréductible. On pose
a. Donner une interprétation de ρ(M) en terme de graphe.
b. Soit λ ∈ ℝ. Montrer que λ est une valeur propre de M si et seulement si 0 est valeur propre de la matrice (− λ) ⊗ M, où (− λ) ⊗ M = (M_(i, j) − λ)_(i, j ∈ {1, …, n}).
c. En déduire que ρ(M) est l'unique valeur propre de M.
d. Montrer qu'il existe K et d tels que pour tout k ≥ K, M^(k + d) = dρ(M) ⊗ M^k.
Question 16 Montrer que ρ(M) est valeur propre de M même si M n'est pas irréductible.
Soit A un automate pondéré dont tous les états sont terminaux. Pour toute suite (u_k)_(k ≥ 1) ∈ Σ^ℕ, on note u[k] = u_1⋯u_k.
Question 17 Montrer qu'il existe λ tel que :
(i) pour toute suite (u_k)_(k ≥ 1), lim_(k → ∞)(L_A(u[k]))/k ≤ λ (si cette limite existe);
(ii) il existe une suite (u_k)_(k ≥ 1) telle que lim_(k → ∞)(L_A(u[k]))/k = λ.
