Sujet 4 (D)
Contexte
Les systèmes à évènements discrets sont un modèle de systèmes dont l'évolution est décrite par une suite d'évènements ponctuels, tels que l'arrivée d'un client, l'activation d'un capteur etc. Pour étudier ces systèmes, on peut associer à chaque évènement une lettre d'un alphabet. Ainsi, une évolution du système est un mot sur l'alphabet qui représente les évènements. On peut alors considérer, par exemple, le langage des comportements valides du système.
Etant donnés une liste d'exemples de comportements valides du système et une liste d'exemples de comportements fautifs, on peut se demander comment estimer le langage (supposé régulier) de tous les comportements valides : c'est ce qu'on appelle l'inférence grammaticale.
L'un des algorithmes les plus simples s'appelle RPNI. Il construit un automate compatible avec les jeux d'exemples valides et fautifs, en essayant de minimiser son nombre d'états (suivant le principe du rasoir d’Ockham).
Dans cet exercice, on va s'intéresser à la première étape de l'algorithme RPNI, qui est de construire l'automate des préfixes du jeu d'exemples positifs, appelé Prefix Tree Acceptor.
Enoncé
On définit le Prefix Tree Acceptor (PTA) d'un ensemble de mots L_pos commme le plus petit automate (en terme de nombre d'états) qui reconnaisse exactement L_pos et tel qu'un état ne soit pas accessible depuis un autre par deux lettres différentes.
Par exemple, pour l'ensemble de mots {ab,bbb,aaa,bba,b}, le PTA est :
Pour l'ensemble de mots {a,b}, la condition sur les états accessibles par deux lettres différentes n'est vérifiée que par le premier des 3 automates suivants (les deux derniers sont d'ailleurs identiques). Le PTA est donc le premier automate, et il a 3 états.
Etant donné un ensemble de mots L_pos (sur l'alphabet composé des lettres de `a` à `z`), déterminer le nombre d'états de son PTA.
Limites de temps et de mémoire (Python)
- Temps : 1 s sur une machine à 1 GHz.
- Mémoire : 8 000 ko.
Entrée
L'entrée est la liste des mots de L_pos, un par ligne.
Sortie
La sortie est le nombre d'états du PTA de L_pos, suivi d'un retour à la ligne.
Exemples
Exemple 1
entrée :
ab bbb aaa bba b
sortie :
9
Exemple 2
entrée :
x xk xkx xkxx xkcd
sortie :
7
Commentaires
Squelettes de codes :
[GROUPFULL:skeleton]