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 fonction binaire_faible de type int → int list qui associe à un entier 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.
Par exemple, pour l’entier 6 (110 en binaire), la fonction renvoie [0; 1; 1].
En déduire une fonction binaire_fort qui décompose un entier en base 2 en plaçant cette fois le bit de poids le plus fort en tête de liste.
Pour le même entier 6, la fonction renvoie [1; 1; 0].
1. Automates déterministes
On choisit de représenter un automate fini déterministe A = (Σ, Q, q₀, F, δ) à l’aide d’un type ’a pour l’ensemble des états Q et d’un type ’b pour l’alphabet Σ.
Voici le type défini pour un automate déterministe :
type ('a, 'b) dfa = {
Start : 'a ;
Accept : 'a list ;
Delta : ('a * 'b * 'a) list
} ;;Question 2
Définir une fonction reconnu de type (’a, ’b) dfa → ’b list → bool qui détermine si l’automate reconnaît un mot de Σ* (représenté par le type ’b list).
Cette fonction doit simuler le parcours de l’automate sur la liste des symboles.
Question 3
Définir une fonction genere_fort de type int → (int, int) dfa qui associe à un entier d un automate déterministe reconnaissant les entiers divisibles par d, lorsque ceux-ci sont lus en base 2 à partir du bit de poids le plus fort.
Pour vérifier la correction de cette fonction, utiliser les fonctions binaire_fort et reconnu définies précédemment.
2. Automates non déterministes
On choisit de représenter un automate fini non déterministe A = (Σ, Q, I, F, δ) par le type suivant :
type ('a, 'b) ndfa = {
Nstart : 'a list ;
Naccept : 'a list ;
Ndelta : ('a * 'b * 'a) list
} ;;Question 4
Pour obtenir un automate non déterministe reconnaissant les entiers divisibles par d à partir du bit de poids le plus faible, à partir d’un automate déterministe généré par genere_fort, il faut inverser l’ordre des bits.
Définir une fonction genere_faible de type int → (int, int) ndfa qui génère un tel automate.
Question 5
Définir une fonction reconnu2 de type (’a, ’b) ndfa → ’b list → bool qui détermine si un automate non déterministe reconnaît un mot de Σ*.
Cette fonction doit gérer les transitions non déterministes et vérifier si au moins un chemin mène à un état final.
Pour vérifier la correction de cette fonction, utiliser les fonctions binaire_faible et reconnu définies précédemment.
FAQ
Qu’est-ce qu’un bit de poids faible et fort ?
Le bit de poids faible est le premier bit à droite (le moins significatif), tandis que le bit de poids fort est le premier bit à gauche (le plus significatif) dans une représentation binaire.
Comment vérifier qu’un automate reconnaît bien les mots attendus ?
Utiliser la fonction de reconnaissance (reconnu ou reconnu2) en appliquant la décomposition binaire (binaire_faible ou binaire_fort) des mots à tester.
Pourquoi utiliser un automate non déterministe pour le bit de poids faible ?
Un automate non déterministe permet de gérer plus facilement les transitions inversées, car il peut explorer plusieurs états simultanément, contrairement à un automate déterministe.