ENS Informatique Fondamentale (Maths Info) MP MPI 2023

VENDREDI 21 AVRIL 2023
14h00-18h00
FILIERES MP et MPI
Epreuve

INFO-FONDAMENTALE (ULSR)

Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve

Le sujet porte sur les automates finis, dont la définition est rappelée dans le préambule. Le sujet s'intéresse à la propriété d'ambiguïté des automates finis, propriété également définie dans le préambule. La première partie lie les notions de déterminisme et d'ambiguïté d'un automate fini en utilisant la notion de miroir d'un automate. La deuxième partie amène à définir un algorithme qui teste si un automate est ambigu et vous demande de déterminer sa complexité asymptotique. La troisième et la quatrième partie étudient la concision des automates non ambigus et ambigus.

Les parties 1 et 2 sont indépendantes; il est conseillé de les traiter en premier car les parties 3 et 4 en dépendent. Il est permis d'admettre les réponses à certaines questions pour répondre aux suivantes.

On note un alphabet fini, c'est à dire un ensemble fini de symboles appelés lettres. Un mot sur est une suite finie de lettres. On note l'ensemble des mots de longueur sur et l'ensemble de tous les mots sur . Soient deux mots sur , on note la concaténation de et . Un langage sur est un sous-ensemble de .

Un automate sur est un tuple où :

La Figure 1 représente graphiquement trois automates. Les symboles dans sont encerclés, avec deux cercles pour les symboles dans . Une transition est représentée par une flèche étiquetée par , allant de l'état source à l'état destination . Les états initiaux sont indiqués par une flèche sans état source.

Un calcul de sur un mot est une suite finie d'états telle que et pour tout . Un tel calcul est dit acceptant si . On dit alors que accepte . Le langage de , noté , est l'ensemble des mots acceptés par .

Un automate est dit déterministe si et pour tout , .

Un automate est dit complet si et pour tout .

Soient et un automate. Le mot est dit ambigu pour s'il existe deux calculs acceptants et de sur avec . On définit , le degré d'ambiguïté de dans , comme étant le nombre de calculs acceptants différents de sur . Ainsi, est ambigu pour si et seulement si . On note l'ensemble des mots ambigus pour . L'automate est dit ambigu si .

Ce sujet s'intéresse tout particulièrement aux automates non ambigus.

Question 1.1 Les trois automates de la Figure 1 acceptent le même langage. Donnez-en, sans justification, une description intuitive.

Question 1.2 Pour chacun des automates de la Figure 1, dites s'il est déterministe ou non déterministe. Justifiez vos affirmations.

Question 1.3 Pour l'automate de la Figure 1, calculez et déduisez en si est ambigu ou non. Faites de même pour les automates et .

Soit un automate. On note l'automate miroir de , défini par :



.
Un automate est dit co-déterministe si son automate miroir est déterministe.

Question 1.4 Soit un automate, un mot accepté par et un calcul acceptant de sur . Montrez qu'il existe un mot tel que soit un calcul acceptant de sur .

Question 1.5 Montrez qu'un automate est ambigu si et seulement si est ambigu.

Question 1.6 Montrez que si un automate est déterministe, alors n'est pas ambigu.

Question 1.7 Montrez que si un automate est co-déterministe, alors n'est pas ambigu.

Question 1.8 Pour chacune des questions suivantes, donnez un automate ayant au plus 4 états et respectant les propriétés demandées. Justifiez vos réponses.
(i) est non ambigu mais ni déterministe, ni co-déterministe;
(ii) est infini et ;
(iii) est infini, et .

Le but de cette partie est d'obtenir un algorithme qui teste si un automate est ambigu et de déterminer sa complexité asymptotique.

Dans cette partie, est un automate tel que .

En utilisant , on définit l'automate comme suit :

;
;
avec:

Question 2.1 Soit le premier automate de la figure Figure 1. Construisez l'automate . Il est inutile de faire figurer les états qui ne sont pas accessibles à partir d'un état initial. Donnez, sans justification, le langage .

Question 2.2 Soient un mot et un calcul de sur . On pose et .
(i) Montrez que et sont des calculs de sur .
(ii) Montrez que si et seulement si .
(iii) Montrez que, si est acceptant, alors et sont acceptants.
(iv) Montrez qu'il existe un calcul tel que et sont acceptants mais ne l'est pas.

Question 2.3 Montrez que .

Pour deux fonctions , on dit que est une borne asymptotique de , et on le note par , s'il existe deux constantes strictement positives et telles que pour tout . Cette définition se généralise naturellement à des fonctions et avec plusieurs paramètres.

Question 2.4 Pour chaque ensemble et , donnez une borne asymptotique au nombre d'éléments qu'il contient en fonction des tailles de et .

Question 2.5 Donnez un algorithme qui a comme entrée et comme sortie en précisant:
(i) quelle structure de données classique (matrice d'adjacence ou liste d'adjacence) est utilisée pour représenter et ,
(ii) une borne asymptotique de la complexité en temps d'exécution de cet algorithme en fonction de la somme des tailles des ensembles et .

Question 2.6 Décrivez une méthode permettant de tester si est ambigu en utilisant l'automate . Donnez une borne asymptotique de la complexité en temps de cette méthode en fonction de la somme des tailles des ensembles et .

Soit un entier strictement positif.

Question 2.7 Soit un mot de longueur .
(i) Donnez, en fonction de et , une borne supérieure sur le degré d'ambiguïté de dans .
(ii) Donnez un automate et un mot de longueur pour lesquels la borne supérieure indiquée ci-dessus est atteinte.

Question 2.8 On pose . Montrez que est régulier.

Question 2.9 On pose . Montrez que est régulier.

Le but de cette partie est de prouver que les automates non ambigus peuvent être exponentiellement plus concis que leurs équivalents déterministes et complets.

Dans toute cette partie, on fixe l'alphabet . Pour un entier, on pose , le langage des mots dont la -ième lettre en partant de la fin est un .

Question 3.1 Donnez un automate non ambigu acceptant , puis donnez un automate déterministe et complet acceptant .

Question 3.2 Montrez que pour tout entier, il existe un automate non ambigu avec états tel que .

Question 3.3 Montrez que pour tout entier, il existe un automate déterministe et complet avec états tel que .

On veut à présent prouver que tout automate déterministe et complet acceptant a au moins états.

Question 3.4 Soit un automate déterministe et complet. Soit . Montrez qu'il existe un unique calcul, non nécessairement acceptant, de sur .

Soit un automate déterministe et complet et . On note l'état atteint par l'unique calcul de sur , c'est-à-dire l'état tel que est un calcul de sur .

Question 3.5 Soit et un automate déterministe et complet reconnaissant . Soient et deux mots de de longueur . Montrez que si et seulement si .

Question 3.6 Soit . Montrez que tout automate déterministe et complet reconnaissant a au moins états.

Le but de cette partie est de prouver que les automates ambigus peuvent être exponentiellement plus concis que leurs équivalents non ambigus.

Pour , on pose un alphabet à lettres et le langage des mots sur dont au moins une lettre apparaît au moins deux fois, c'est-à-dire :

Question 4.1 Pour ,
(i) donnez un automate acceptant et ayant au plus 5 états,
(ii) donnez un automate non ambigu acceptant et ayant au plus 9 états.

Question 4.2 Montrez que pour tout , il existe un automate avec au plus états acceptant .

Question 4.3 Montrez que pour tout , il existe un automate non ambigu avec au plus états acceptant .

On veut à présent prouver que tout automate non ambigu acceptant a au moins états. Jusqu'à la fin de cette partie, on fixe un entier et un automate non ambigu acceptant .

Soient et deux mots de . Lorsque , on note l'état de atteint après avoir lu lors de l'unique calcul acceptant de sur . Autrement dit, soit et l'unique calcul acceptant de sur , alors .

Question 4.4 Soient et quatre mots de tels que et . On suppose que .
(i) Montrez que et .
(ii) Montrez que .

L'objectif à présent est de prouver que ces contraintes garantissent que a au moins états.

Soit une suite de mots et une lettre. On note la suite ( ), c'est-à-dire la suite obtenue en ajoutant à la fin de chaque mot de .

On fixe un ordre total , et on note avec pour tout , . On construit une famille de suites de mots de comme suit :

Finalement, on pose . Par exemple, pour et , la suite contient 4 éléments : .

Finalement, on remarque que contient éléments et on pose la matrice de dimension à coefficients en définie par :

Par exemple, est donnée ci-dessous :

Question 4.5 Montrez que peut s'écrire sous la forme:

où, pour est la matrice carrée de dimension dont tous les coefficients valent 1 .

Question 4.6 Soient et . Montrez que si et seulement si .

À chaque état de , on associe le vecteur colonne de dimension défini par :

Question 4.7 Montrez que l'ensemble de vecteurs est une famille génératrice du sousespace vectoriel engendré par les vecteurs colonnes de .
Indication : Soit la -ème colonne de . On pourra montrer que est une combinaison linéaire de vecteurs de en prouvant que :

Question 4.8 Montrez que est de rang .

Question 4.9 En déduire que contient au moins états tels que .

Question 4.10 Montrez que si , alors et .

Question 4.11 Conclure que a au moins états.