ENS Informatique Fondamentale (Maths Info) MP 2015

(Durée : 4 heures)

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.

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.

On appelle automate pondéré un automate fini dont les arêtes ont un poids. Plus précisément, c'est un sextuplet , où

Un chemin dans l'automate est une suite finie de transitions avec et tels que . Ce chemin est un cycle si et c'est un cycle élémentaire s'il n'existe pas tel que . Enfin, ce chemin est sans cycle s'il n'existe pas tel que ( ) est un cycle.

L'entier est la longueur de ce chemin; le mot est le mot (ou étiquette) de ce chemin; et le poids de ce chemin est

Ce chemin est dit acceptant si et . Si un mot est accepté par l'automate s'il existe un chemin acceptant de mot . Le poids d'un mot dans l'automate est le poids maximal d'un chemin acceptant de mot . Si un tel chemin n'existe pas, alors par convention, le poids du mot est :

Un langage pondéré sur un alphabet fini est un ensemble tel qu'il existe tel que . Le poids de dans est , et on note le support du langage.

Le langage est le langage pondéré reconnu par l'automate : pour tout mot .

On supposera dans tout le problème que tous les états des automates pondérés sont utiles : pour tout état , il existe et tels qu'il existe un chemin de à et un chemin de à .

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 est un langage reconnu par un automate fini, il est possible de trouver un automate pondéré de support tel que .

Question 2 On pose .
a. Quel est le langage pondéré sur reconnu par l'automate pondéré suivant? La notation " "signifie que la transition est étiquetée par et de poids . 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 , où (respectivement ) est le nombre d'occurrences de (respectivement ) dans .

On fixe . On s'intéresse au problème de savoir si tous les poids des mots reconnus par un automate pondéré sont inférieurs à .

On note le langage pondéré reconnu par l'automate pondéré .

a. Montrer que pour tout mot si et seulement si tous les chemins acceptants de d'étiquette sont de poids inférieur ou égal à .
b. Montrer que l'on a l'équivalence entre les deux assertions :
(i) .
(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 à .

Dans cette partie on s'intéresse aux deux automates et suivants, où .

Soient et . Considérons l'espace probabilisé ( ) tel que pour tout et et tel que les événements forment une famille mutuellement indépendante. Si est une variable aléatoire sur , on note son espérance et sa variance.

Question 4 Soit . Calculer .
Soit une variable aléatoire sur .
Question 5 On s'intéresse dans cette question à l'automate . On pose .
a. Calculer et . (On rappelle que est le nombre d'occurrences de dans .)
b. Montrer que pour tout , il existe tel que et que pour tout , il existe tel que .
c. Quel est le langage pondéré reconnu par l'automate ?
d. Déduire des questions précédentes que (Indication : on pourra d'abord montrer que pour tout , il existe tel que .

Question 6 On s'intéresse maintenant à l'automate . On note l'état obtenu après lecture du mot , le préfixe de de longueur , (ici, on a donc ).
a. Pour tout , calculer .
b. En déduire et .
c. En déduire . (Indication : on pourra s'intéresser à ).

Soit . On appelle matrice pondérée une matrice à coefficients dans . Soient deux matrices pondérées. On définit les opérations suivantes :
par ;

Un vecteur pondéré est un élément de (vecteur ligne) ou (vecteur colonne). On définit de la même manière

a. Montrer que l'opération est associative : pour tous .
b. Montrer que l'opération est commutative : pour tous .
c. Montrer que l'opération est associative : pour tous .
d. Montrer que l'opération est distributive sur et .
e. Donner une matrice telle que pour tout .

Soit . On pose et pour tout .
Une matrice peut être représentée par un graphe orienté et pondéré ( ) dont l'ensemble des sommets est , l'ensemble des arcs est , et la fonction de pondération est .

Question 8 Montrer que est égal au poids maximal d'un chemin de longueur de vers dans (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 vers de longueur , ce poids est ).

Soit un automate pondéré avec . Pour tout , soit la matrice du graphe pondéré obtenu en ne gardant que les transitions d'étiquette
, avec et . Pour tout , on pose avec la convention si est le mot vide.

a. Soient . Montrer que le poids maximum d'un chemin d'étiquette de vers est égal à .
b. En déduire une expression matricielle pour , c'est-à-dire de la forme où 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.

a. Considérons la matrice et . Montrer que 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 .
c. Soit le poids maximal d'un chemin de vers passant uniquement par des sommets intermédiaires tels que ( et non compris). On pose . Exprimer en fonction de . En déduire un algorithme par programmation dynamique qui calcule .
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 à et faux sinon, sans faire d'hypothèse a priori sur les poids des cycles de l'automate.

On dit qu'une matrice pondérée est irréductible si le graphe orienté qui lui est associé est fortement connexe. Soit 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 associé à la valeur propre un vecteur tel que , où est le vecteur .

Soient . On note si pour tout et de la même manière, on note si pour tout .

Question 11 Soient et tels que .
a. Montrer que pour tout puis que .
b. En déduire que .

Question 12 Soient et tels que .
a. Montrer que pour tout il existe tel que .
b. En déduire que .

Soit l'ensemble des sommets de qui sont sur un cycle de poids 0 .

Question 13 Montrer que pour , le -ème vecteur colonne de est un vecteur propre pour . Quel est l'ensemble des valeurs propres de ?

Pour et , on note le poids du chemin le plus lourd de vers de longueur et passant par .

a. Montrer qu'il existe tel que pour tout .
b. Soient et . Montrer qu'il existe tel que pour tout , .
c. Soient . Montrer qu'il existe tel que pour tout .
d. En déduire qu'il existe et tels que pour tout .

On se place maintenant dans le cas où le cycle de poids maximal n'est plus égal à 0 , mais la matrice est toujours irréductible. On pose

a. Donner une interprétation de en terme de graphe.
b. Soit . Montrer que est une valeur propre de si et seulement si 0 est valeur propre de la matrice , où .
c. En déduire que est l'unique valeur propre de .
d. Montrer qu'il existe et tels que pour tout .

Question 16 Montrer que est valeur propre de même si n'est pas irréductible.

Soit un automate pondéré dont tous les états sont terminaux. Pour toute suite , on note .

Question 17 Montrer qu'il existe tel que :
(i) pour toute suite (si cette limite existe);
(ii) il existe une suite telle que .