Chapitre 7 TP Python
Le but de ce TP est de mettre en oeuvre quelques algorithmes et manipulations vus sur les automates pendant le cours.
Le rendu prendra la forme du Jupyter Notebook (.ipynb) que vous pourrez éditer en utilisant Jupyter lab directement en lançant la commande
jupyter lab
Il faut au préalable avoir installé Jupyter https://jupyterlab.readthedocs.io/en/latest/index.html. Il aussi possible d’éditer des notebooks Jupyter avec Visual Studio Code. Il est aussi possible d’éditer des Notebooks Jupyter en ligne (https://Jupyter.org ou https://mydocker.gitlab.dsi.universite-paris-saclay.fr) mais pour ce TP, il faudra installer plusieurs bibliothèques, ce qui pourrait être plus difficile sur ces sites.
7.1 La bibliothèque automata
Pour ce TP, nous allons utiliser la bibliothèque automata qui fournit une classe pour les automates déterministes (et aussi d’autres automates plus généraux) avec beaucoup de méthodes associées.
La documentation se trouve à cette adresse : https://caleb531.github.io/automata/
Pour installer cette bibliothèque, vous pouvez entrer cette commande dans un bloc de code Python dans votre notebook Jupyter (ou simplement la commande pip dans un terminal) :
Pour représenter garphiquement les automates vous aurez aussi besoin d’installer Graphviz (et éventuellement Coloraide) avec les commandes suivantes
Vous pouvez maintenant créer votre premier automate dans la classe “DFA” qui siginifie deterministic finite automata :
from automata.fa.dfa import DFA
automate = DFA(
states={'q0', 'q1', 'q2'},
input_symbols={'0', '1'},
transitions={
'q0': {'0': 'q0', '1': 'q1'},
'q1': {'0': 'q0', '1': 'q2'},
'q2': {'0': 'q2', '1': 'q1'}
},
initial_state='q0',
final_states={'q1'}
)On voit qu’un automate est la donée d’un ensemble d’états, d’un ensemble de transitions (c’est-à-dire un alphabet comme vu en cours), d’un dictionnaire de transisitons, d’un état initial et d’un ensemble détats finaux.
Pour afficher un automate on peut utiliser les deux commandes suivantes. La première (print) donnera juste les ensembles qui définissent l’automate alors que la seconde se repose sur graphviz pour donner une représentation sagittale de l’automate.
Par exemple pour l’automate ci-dessus, on obtient le graphe ci-dessous
Figure 7.1: Affichage de l’automate
Exercice 7.1 Créer quelques automates vus en cours, dans la classe DFA et doner la représentation sagitalle associée. Vous préciserez le langage reconnu
7.2 Utilisations des méthodes de la bibliothèque automata-lib
La bibliothèque automata étant riche en méthodes (implémentant toutes les manipulations sur les automtates vues en cours), nous allons nous reposer dessus et ne pas tout réécrire.
La documentation n’est pas complète mais le code source est disponible à cette adresse : https://github.com/caleb531/automata/blob/main/automata/fa/dfa.py. Il est largement commenté. Une recherche par mot clé (en anglais) devrait vous permettre de trouver les méthodes désirées. Le fichier dfa.py contient les méthodes spécifiques aux automates déterministes. Pour les automates non-déterministes, il faudra regarder dans le fichier gnfa.py.
Exercice 7.2 Vous trouverez des méthodes de la bibliothèque automata pour illustrer les points suivants avec des exemples d’automates de votre choix. Vous mettrez en forme pour que ce soit le plus clair possible.
- Déterminer si un automate déterministe est complet.
- Compléter un automate déterministe.
- Vérifier si un mot particulier est reconnu par l’automate.
Exercice 7.3 Vous trouverez des méthodes de la bibliothèque automata pour illustrer les manipulations suivants avec des exemples d’automates de votre choix. Vous mettrez en forme pour que ce soit le plus clair possible et vous donnerez les langages correspondants.
- Construction de l’automate qui reconnait l’intersection de deux langages.
- Construction de l’automate qui reconnait le complémentaire d’un langage.
- Construction de l’automate qui reconnait l’union de deux langages.
La bibliothèque automata contient aussi des méthodes pour créer des automates à partir d’expression régulière (voir le fichier https://github.com/caleb531/automata/blob/main/automata/regex). Vous prendrez garde au fait que la syntaxe pour les expressions régulières n’est pas tout à fait la même que celle vue en cours mais cela est précisé en commentaires au début du fichier.
Exercice 7.4 Pour chaque langage de l’Exercice 6.1, vous donnerez l’expression régulière correspondante et utiliserez les méthodes de bibliothèque automata pour donner un automate déterministe qui reconnaît le langage associé.
Vous aurez peut-être besoin d’utiliser des automates non déterministes. Vous pourrez alors utiliser la classe NFA (https://github.com/caleb531/automata/blob/main/automata/fa/nfa.py)
7.3 Langage mirroir
La bibliothèque automata contient de nombreuses méthodes qui réalisent les algorithmes vus en cours. Nous allons ici voir un procédé qui n’est pas dans cette bibliothèque.
Définition 7.1 Soit \(m=m_1\dots m_n\) un mot sur l’alphabet \(\mathcal{A}\). Le mirroir de \(m\) est le mot \(m_n\dots m_1\).
Si \(L\) est un langage sur \(\mathcal{A}\), le mirroir noté \(L'\) de \(L\) est l’ensemble des miroirs de mots de \(L\).
Par exemple, le mot mirroir de \(abc\) est \(cba\).
Exercice 7.5 Justifier théoriquement que si \(L\) est un langage régulier alors \(L'\) est aussi un langage régulier.
Exercice 7.6 Écrire une fonction python qui prend en entrée un automate de la classe DFA, reconnaissant un langage \(L\), et retourne un automate de la classe DFA reconnaissant le langage mirroir \(L'\).
Exercice 7.7 Appliquer votre fonction à plusieurs automates de votre choix en précsisant les langages \(L\) et \(L'\) à chaque fois.