On découvre ici un module, FSA (Finite State Automaton), permettant de manipuler des automates : déterminisation, minimisation, représentation graphique, etc.

Installation

Préliminaires

Pour avoir le droit d'installer ce module en salle de TP, il nous faut un environnement virtuel de travail.

• Si vous avez déjà votre environnement de travail, lancez-le.
• Sinon, créer un environnement (à faire dans un terminal) :

  guyeux@kerry:~$ virtualenv monenv

  guyeux@kerry:~$ source monenv/bin/activate

La première ligne (qui crée l'environnement) n'est à faire qu'une seule fois. La seconde sera à faire à chaque fois que vous voudrez travailler dans votre environnement virtuel.

Dans tous les cas, vous êtes maintenant dans votre environnement virtuel, et on peut télécharger, puis installer le module...

Télécharger le module

Vous pouvez récupérer le module FSA ici, ou sur le site d'origine, le décompresser :

  (mon_env)guyeux@kerry:~$ unzip FSA-1.0.zip

puis allez dans le répertoire créé.

Installation du module

Pour l’installer, il faut commencer par créer un fichier LICENSE.txt manquant :

  (mon_env)guyeux@kerry:~$ cd FSA-1.0
  (mon_env)guyeux@kerry:~$ cat > LICENSE.txt

Tapez ensuite sur Ctrl-D.

Vous pouvez maintenant réaliser l'installation du module :

  (mon_env)guyeux@kerry:FSA-1.0/$ python setup.py install

Une fois python lancé, tapez

  >>> from FSA import *

Utilisation

Création d'un automate

La création

Pour créer un automate fini déterministe avec le module FSA, il faut passer au constructeur :

• La liste des états (states).
• L'alphabet avec lequel on étiquette les flèches.
• Les transitions : une liste de triplets (sommet initial, sommet final, étiquette de transition).
• L'état initial.
• La liste des états finaux.

Comme suit :

  >>> automate = FSA(states = [1,2,3,4], 
                    alphabet = ['a','b','c'], 
                    transitions = [(1,2,'a'),(1,3,'c'),(2,3,'b'),(3,4,'b')], 
                    initialState = 1,  
                    finalStates = [3,4])

Visualisation

On peut visualiser cet automate avec la méthode view() :

  >>> automate.view()

Le résultat est le suivant :

Accession aux attributs

On peut accéder, pour chaque automate ainsi créé, à tous ses attributs (état initial, transitions, etc.), comme suit :

  >>> print automate.initialState
  1
  >>> print automate.transitions
  [(1, 2, 'a'), (1, 3, 'c'), (2, 3, 'b'), (3, 4, 'b')]

Quelques méthodes pour l'automate

Connaître le prochain état du système

Quand l'automate est dans l'état 1, et qu'il reçoit l'entrée 'a', alors il évolue dans l'état 2. En effet :

  >>> automate.nextState(1,'a')
  2

Relever les transitions sortant d'un état

Pour savoir quelles transitions partent de l'état 1 :

  >>> automate.transitionsFrom(1)
  [(1, 2, 'a'), (1, 3, 'c')]

Savoir si un automate reconnaît une chaîne donnée

L'automate ci-dessus reconnaît l'expression abb, mais pas aab. On peut le vérifier ainsi :

  >>> automate.accepts('abb')
  True
  >>> automate.accepts('aab')
  False

Ajout/suppression d'une transition, d'un état

Pour rajouter, ou supprimer des transitions, il suffit de modifier l'attribut transition de l'automate, qui est une liste. Par exemple, pour rajouter une boucle à l'état 1 de notre exemple :

  >>> automate.transitions
  [(1, 2, 'a'), (1, 3, 'c'), (2, 3, 'b'), (3, 4, 'b')]
  >>> automate.transitions.append((1,1,'a'))
  >>> automate.transitions
  [(1, 2, 'a'), (1, 3, 'c'), (2, 3, 'b'), (3, 4, 'b'), (1, 1, 'a')]
  >>> automate.view()

Ce qui affiche :

Pour ajouter ou supprimer un état, un état final, etc. on procède de la même manière.

Travaux pratiques

1. Créer une fonction qui reçoit un automate, et qui affiche proprement sa table de transition.
2. Faire une fonction qui teste si un automate donné est déterministe.
3. Reprendre les exercices de la page sur les automates finis, et vérifier vos résultats avec le module FSA.