Théorie des langages : Td 1 automates
Télécharger PDFTravaux pratiques
option informatique
Simulation d’un automate
Préliminaire
Question 1.
Définir une fonctionbinaire_faiblede typeint−> int listqui a un entier associe la liste des bits de sa
décomposition en base 2, le bit de poids le plus faible se trouvant en tête de liste.
En déduire une fonctionbinaire_fortqui décompose un entier en base 2 en plaçant cette fois le bit de poids le plus fort
en tête de liste.
1. Automates déterministes
On choisit de représenter un automate fini déterministeA= (Σ,Q, q0 ,F,δ) à l’aide d’un type’apour l’ensemble des étatsQ
et d’un type’bpour l’alphabetΣ. Ceci nous amène à définir le type :
type(’a, ’b) dfa = {Start: ’a ;
Accept: ’a list ;
Delta: ((’a*’b)*’a) list} ;;
Question 2.Définir une fonctionreconnude type(’a, ’b) dfa−> ’b list−> boolqui détermine si automate reconnait un motdeΣ ∗
(représenté par le type’b list).
Question 3.Définir une fonctiongenere_fortde typeint−> (int, int) dfaqui à un entierdassocie un automate qui
reconnait les entiers divisibles pardlorsque ceux-ci sont lus en base 2 à partir du bit de poids le plus fort.
On pourra vérifier la correction de cette fonction à l’aide des fonctions définies aux questions 1 et 2.
2. Automates non déterministes
On choisit de représenter un automate fini non déterministe A = (Σ,Q,I,F,δ) par le type :
type(’a, ’b) ndfa = {Nstart: ’a list ;
Naccept: ’a list ;
Ndelta: ((’a*’b)*’a) list} ;;
Question 4.Comment peut-on, à partir d’un automate déterministe obtenu par la fonctiongenere_fortde la question
3, obtenir un automatenon déterministequi reconnait les entiers divisibles pardlorsque ceux-ci sont lus à partir du bit de
poids le plus faible ?
Rédiger une fonctiongenere_faiblede typeint−> (int, int) ndfaqui génère un tel automate.
Question 5.
Définir une fonctionreconnu2de type(’a, ’b) ndfa−> ’b list−> boolqui détermine si un automate non déter-
ministe reconnait un mot deΣ∗ .
Vérifier la correction de cette fonction à l’aide des fonctions définies aux questions 1 et 4.
page 1