Implémentation d’un AFD en Python

Bienvenue dans ce deuxième article de la série sur les automates. Aujourd’hui, nous allons nous intéresser particulièrement aux bases de notre implémentation en Python.

Avant de commencer

Le choix de Python me semble adéquat puisqu’il permettra d’illustrer simplement les différents algorithmes liés aux automates dans les prochains chapitres, tout en profitant de interpréteur pour faciliter les manipulation.

Cette implémentation se concentrera sur l’objectif d’avoir des outils de manipulation d’automates simples. La question des performances sera parfois abordées, mais il ne s’agit pas de l’aspect principal de cet article.

De la même façon, si on peut discuter longtemps des différentes approches pour proposer une API de manipulation d’automates, il s’agira avant tout d’avoir un code simple à utiliser. Notamment, le support des AFND et des AFND-ε pour les chapitres suivants ne sera pas considéré dans cet article (même si l’implémentation que je vous propose ne demandera pas beaucoup de modifications lorsque nous en serons arrivés là).

Cet article se divise en cinq parties :

Modélisation d’un automate
Implémentation de cette solution
Implémentation de l’exécution d’un mot donné.
Comment sauvegarder/charger un automate, de manière ne pas avoir à reconstruire un automate lorsqu’on relance l’interpréteur.
Comment visualiser notre automate.

Modélisation d’un automate

La première question qu’il nous faut nous poser est la manière dont on va représenter un automate.

Plusieurs solutions peuvent être envisagées, chacune proposant leurs propres avantages d’un point de vue design de logiciel. Nous allons ici en regarder quelques unes rapidement mais il ne s’agit pas de présenter toutes les solutions possibles.

Pour modéliser un automate, il va falloir trouver le moyen de représenter l’alphabet, les états, les différentes transitions ainsi que l’état initial et les états accepteurs.

Dans un premier temps, je vous propose de regrouper tous ces éléments au sein d’un même classe, DFA, qui correspondra à un automate fini déterministe. Si on imagine assez facilement que l’alphabet puisse être remplacé par une chaîne de caractère contenant tous les symboles, la question des états et des transitions est plus complexe.

Nous allons mettre de côté les approches orientées graphes, telles que les matrices d’adjacences, d’incidences etc. Celles-ci ont des avantages certains d’optimisation mais il ne s’agit pas ici d’un cours de théorie des graphes et je vais donc partir du principe que c’est un domaine inconnu du lecteur.

Une approche possible est de créer les classes suivantes :

Transition : contenant l’état d’origine, l’état de destination et le symbole associé.
State : qui contiendra une liste de transitions, et éventuellement un nom.

Cette méthode est assez facile à conceptualiser mais est un peu lourde. L’autre solution que je vous propose d’utiliser ici, est de ne pas créer de classe supplémentaire, ce qui nous permettra d’avoir une seule classe DFA à développer et qui nous fera globalement moins de code à écrire.

En effet, la question de l’identification des états est importante pour pouvoir définir d’où part et où arrive une transition (et également pour la manipulation d’un automate en général). Si on décide de stocker nos états dans une liste dans la classe DFA, on peut décider de les identifier par indice dans cette liste. On peut aussi utiliser des adresses (difficile en python), ou un nom etc.

Imposer un nom unique pour les états permet de représenter les états par une liste de chaîne de caractères et m’a semblé ici la solution la plus simple à mettre en place. Les états seront donc de simples strings et nous ajouterons donc dans notre classe DFA une liste de strings supplémentaire correspondant aux états finaux et une chaîne de caractère qui sera l’état initial.

La dernière question est donc la façon dont on va représenter les transitions de l’automate. Une transition associe deux états et un symbole. Une solution parmi d’autres, mais qui à l’avantage de proposer une bonne syntaxe d’utilisation (et d’être utile pour les automates non-deterministe par la suite) est d’utiliser un dictionnaire associant l’état d’origine de la transition (son nom) à une paire (symbole, état-cible). Cette méthode nous permettrait de trouver l’état de destination pour un symbole et un état d’origine donné de cette manière :

for (symbol, dst_state) in self.transitions[src_state]:
    if symbol == required_symbol:
        return dst_state
return None

for (symbol, dst_state) in self.transitions[src_state]:

if symbol == required_symbol:

return dst_state

return None

L’état initial étant unique, il nous suffit d’avoir un attribut correspondant au nom de l’état initial. De la même manière un attribut contiendra le nom des états finaux :

def print_state_infos(dfa, state):
    if state == dfa.init:
        print("L'état est initial.")
    if state in dfa.finals:
        print("L'état est final.")

def print_state_infos(dfa, state):

if state == dfa.init:

print("L'état est initial.")

if state in dfa.finals:

print("L'état est final.")

L’implémentation

Pour résumer le design que nous avons choisi, un automate est représenté par la classe DFA, qui va contenir :

Un alphabet (représenté par une chaîne de caractères).
Une liste d’états, qui seront représentés par leur nom.
Le nom de l’état initial.
Une liste d’états finaux, encore une fois leurs noms.
Les transitions, représentés par un dictionnaire associant une chaîne de caractère (le nom de l’état d’origine), avec une paire symbole / état-cible.

Ci-suit donc la classe DFA et son constructeur :

class DFA:
    """ This class represent any type of deterministic finite automaton."""
    def __init__(self, alphabet):
        """ Initialise the finite automaton.
            @param the alphabet of the automaton."""

        """ List of string corresponding to states name.
            States are always identificated by name."""
        self.states = []
        """ Dictionary using src state as key and mapping it to a list of
            pair (dest_state, symbol)."""
        self.transitions = {}
        """ The string corresponding to the name of the initial state."""
        self.init = None
        """ A list containing the name of the final states."""
        self.finals = []
        """ A string containing all symbols in the alphabet."""
        self.alphabet = ""
        for s in alphabet:
            if s not in self.alphabet:
                self.alphabet += s

class DFA:

""" This class represent any type of deterministic finite automaton."""

def __init__(self, alphabet):

""" Initialise the finite automaton.

@param the alphabet of the automaton."""

""" List of string corresponding to states name.

States are always identificated by name."""

self.states = []

""" Dictionary using src state as key and mapping it to a list of

pair (dest_state, symbol)."""

self.transitions = {}

""" The string corresponding to the name of the initial state."""

self.init = None

""" A list containing the name of the final states."""

self.finals = []

""" A string containing all symbols in the alphabet."""

self.alphabet = ""

for s in alphabet:

if s not in self.alphabet:

self.alphabet += s

Vous constaterez que j’ai fait ici le choix de laisser tous les attributs en public. Le Python ne dispose pas d’une portée privée stricte mais l’usage est de préfixer dans ce cas la variable par un underscore (la technique de name mangling avec le double underscore est également possible), mais il aurait pu être intéressant de proposer une veritable encapsulation. Cela aurait cependant alourdi l’interface et on peut très bien s’en passer ici.

L’état initial est ainsi par défaut à None, et peut être directement modifié après la création de l’automate.

Nous allons maintenant nous intéresser aux deux parties un peu plus complexes : l’ajout d’un état et l’ajout de transition. L’ajout d’état est plus simple puisqu’il nous faut simplement nous assurer que le nom n’est pas déjà utilisé :

def add_state(self, state, final = False):
    """ Add a new state. Print error if the state already exists.
        @param state    the name of the new state.
        @param final    a boolean determining if the state is
            final"""
    if state in self.states:
        print("error : state '" + state + "' already exists.")
        return
    self.transitions[state] = []
    self.states.append(state)
    if final:
        self.finals.append(state)

def add_state(self, state, final = False):

""" Add a new state. Print error if the state already exists.

@param state the name of the new state.

@param final a boolean determining if the state is

final"""

if state in self.states:

print("error : state '" + state + "' already exists.")

return

self.transitions[state] = []

self.states.append(state)

if final:

self.finals.append(state)

L’ajout de transition demande quant à lui de s’assurer que les états et le symbole sont valides puis de vérifier que la transition n’existe pas encore pour l’état d’origine et le symbole donné. Nous allons donc également introduire les fonctions valid_symbol et dst_state qui nous simplifieront la tâche :

def valid_symbol(self, symbol):
    """ Returns true if the symbol is part of the alphabet,
        false otherwise.
        @param symbol the symbol to be tested """
    if symbol not in self.alphabet: return False
    return True

def dst_state(self, src_state, symbol):
    """ Search the transition corresponding to the specified source state
        and symbol and returns the destination state. If the transition does
        not exists, return None.
        @param src_state the source state of the transition.
        @param symbol the symbol of the transition. """
    if src_state not in self.states:
        print("error : the state '" + src_state + "' is not an existing state.")
        return
    for (s, dst_state) in self.transitions[src_state]:
        if s == symbol:
            return dst_state
    return None

def add_transition(self, src_state, symbol, dst_state):
    """ Add a transition to the FA. Print error if the automaton already have a
        transition for the specified source state and symbol.
        @param src_state the name of the source state.
        @param symbol the symbol of the transition
        @param dst_state the name of the destination state."""
    if not self.valid_symbol(symbol):
        print("error : the symbol '" + symbol + "' is not part of the alphabet.")
        return
    if src_state not in self.states:
        print("error : the state '" + src_state + "' is not an existing state.")
        return
    if dst_state not in self.states:
        print("error : the state '" + dst_state + "' is not an existing state.")
        return

    if self.dst_state(src_state, symbol) != None:
        print("error : the transition (" + src_state + ", " + symbol + ", ...) already exists.")
        return

    self.transitions[src_state].append((symbol, dst_state))

def valid_symbol(self, symbol):

""" Returns true if the symbol is part of the alphabet,

false otherwise.

@param symbol the symbol to be tested """

if symbol not in self.alphabet: return False

return True

def dst_state(self, src_state, symbol):

""" Search the transition corresponding to the specified source state

and symbol and returns the destination state. If the transition does

not exists, return None.

@param src_state the source state of the transition.

@param symbol the symbol of the transition. """

if src_state not in self.states:

print("error : the state '" + src_state + "' is not an existing state.")

return

for (s, dst_state) in self.transitions[src_state]:

if s == symbol:

return dst_state

return None

def add_transition(self, src_state, symbol, dst_state):

""" Add a transition to the FA. Print error if the automaton already have a

transition for the specified source state and symbol.

@param src_state the name of the source state.

@param symbol the symbol of the transition

@param dst_state the name of the destination state."""

if not self.valid_symbol(symbol):

print("error : the symbol '" + symbol + "' is not part of the alphabet.")

return

if src_state not in self.states:

print("error : the state '" + src_state + "' is not an existing state.")

return

if dst_state not in self.states:

print("error : the state '" + dst_state + "' is not an existing state.")

return

if self.dst_state(src_state, symbol) != None:

print("error : the transition (" + src_state + ", " + symbol + ", ...) already exists.")

return

self.transitions[src_state].append((symbol, dst_state))

Nous avons maintenant pratiquement tout ce qu’il nous faut pour les algorithmes qui vont suivre. Nous allons aussi surcharger __str__ de manière à avoir possibilité d’afficher nos automates :

def __str__(self):
    ret = "FA :\n"
    ret += "   - alphabet   : '" + self.alphabet + "'\n"
    ret += "   - init       : " + str(self.init) + "\n"
    ret += "   - finals     : " + str(self.finals) + "\n"
    ret += "   - states (%d) :\n" % (len(self.states))
    for state in self.states:
        ret += "       - (%s)" % (state)
        if len(self.transitions[state]) is 0:
            ret += ".\n"
        else:
            ret += ret + ":\n"
            for (sym, dest) in self.transitions[state]:
                ret += ret + "          --(%s)--> (%s)\n" % (sym, dest)
    return ret

def __str__(self):

ret = "FA :\n"

ret += " - alphabet : '" + self.alphabet + "'\n"

ret += " - init : " + str(self.init) + "\n"

ret += " - finals : " + str(self.finals) + "\n"

ret += " - states (%d) :\n" % (len(self.states))

for state in self.states:

ret += " - (%s)" % (state)

if len(self.transitions[state]) is 0:

ret += ".\n"

else:

ret += ret + ":\n"

for (sym, dest) in self.transitions[state]:

ret += ret + " --(%s)--> (%s)\n" % (sym, dest)

return ret

Je vous propose donc de reprendre l’automate du premier chapitre reconnaissant les mots contenant au moins une fois le symbole a sur l’alphabet “ab” :

Et d’utiliser notre module pour créer l’automate équivalent :

~/aumal/src$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17) 
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import DFA
>>> a = DFA.DFA("ab")
>>> a.add_state("0")
>>> a.add_state("1", True)
>>> a.init = "0"
>>> a.add_transition("0", "a", "1")
>>> a.add_transition("0", "b", "0")
>>> a.add_transition("1", "a", "1")
>>> a.add_transition("1", "b", "1")
>>> print(a)
FA :
   - alphabet   : 'ab'
   - init       : 0
   - finals     : ['1']
   - states (2) :
       - (0):
          --(a)--> (1)
          --(b)--> (0)
       - (1):
          --(a)--> (1)
          --(b)--> (1)

>>>

~/aumal/src$ python3

Python 3.6.7 (default, Oct 22 2018, 11:32:17)

[GCC 8.2.0] on linux

Type "help", "copyright", "credits" or "license" for more information.

>>> import DFA

>>> a = DFA.DFA("ab")

>>> a.add_state("0")

>>> a.add_state("1", True)

>>> a.init = "0"

>>> a.add_transition("0", "a", "1")

>>> a.add_transition("0", "b", "0")

>>> a.add_transition("1", "a", "1")

>>> a.add_transition("1", "b", "1")

>>> print(a)

FA :

- alphabet : 'ab'

- init : 0

- finals : ['1']

- states (2) :

- (0):

--(a)--> (1)

--(b)--> (0)

- (1):

--(a)--> (1)

--(b)--> (1)

>>>

Et voilà ! On peut aussi s’amuser à tester les autres fonctions :

>>> a.add_state("0")
error : state '0' already exists.
>>> a.dst_state("0", "b")
'0'
>>> a.dst_state("42", "b")
error : the state '42' is not an existing state.
>>> a.add_transition("0", "c", "w")
error : the symbol 'c' is not part of the alphabet.
>>> a.add_transition("0", "a", "w")
error : the state 'w' is not an existing state.
>>> a.add_transition("0", "a", "0")
error : the transition (0, a, ...) already exists.
>>>

>>> a.add_state("0")

error : state '0' already exists.

>>> a.dst_state("0", "b")

'0'

>>> a.dst_state("42", "b")

error : the state '42' is not an existing state.

>>> a.add_transition("0", "c", "w")

error : the symbol 'c' is not part of the alphabet.

>>> a.add_transition("0", "a", "w")

error : the state 'w' is not an existing state.

>>> a.add_transition("0", "a", "0")

error : the transition (0, a, ...) already exists.

>>>

Avant de clore l’implémentation des fonctions de ce fichier, je vous propose tout de même d’ajouter la méthode clone, qui permettra de faire une copie (complète) de l’automate :

import copy

#...

def clone(self):
    """ Returns a copy of the DFA."""
    a = DFA(self.alphabet)
    a.states = self.states.copy()
    a.init = self.init
    a.finals = self.finals
    a.transitions = copy.deepcopy(self.transitions)
    return a

import copy

#...

def clone(self):

""" Returns a copy of the DFA."""

a = DFA(self.alphabet)

a.states = self.states.copy()

a.init = self.init

a.finals = self.finals

a.transitions = copy.deepcopy(self.transitions)

return a

Une possibilité d’amélioration serait de fournir des méthodes pour la suppression d’états, de transitions ou de symboles par exemple. On verra pour la suite, ce n’est pas indispensable pour le moment.

Exécution d’un automate

Nous allons maintenant nous centrer sur l’exécution de l’automate sur un mot donné. Je vous propose de mettre cette fonction dans le fichier algorithms.py :

""" algorithms.py """

def run(dfa, word):
     pass

""" algorithms.py """

def run(dfa, word):

pass

L’algorithme d’éxécution est relativement simple. On démarre à l’état initial, et pour chaque symbole du mot, on se rend à l’état correspondant à la transition pour ce symbole et l’état courant. Si on rencontre un symbole pour lequel il n’existe pas de transition, le mot est refusé.

Si à l’inverse on arrive à la fin du mot, il nous suffit de regarder si le dernier état atteint est accepteur. Si c’est le cas le mot est accepté, sinon il est refusé. Voici donc une implémentation de cette algorithme :

def run(dfa, word):
    current_state = dfa.init

    for symbol in word:
        next_state = dfa.dst_state(current_state, symbol)
        if next_state is None:
            return False;

        current_state = next_state
        i = i+1

    if current_state in dfa.finals:
        return True
    return False

def run(dfa, word):

current_state = dfa.init

for symbol in word:

next_state = dfa.dst_state(current_state, symbol)

if next_state is None:

return False;

current_state = next_state

i = i+1

if current_state in dfa.finals:

return True

return False

De manière à rendre ça plus visuel, je vous propose d’ajouter des messages d’erreurs et des informations sur l’état de l’exécution. Pour ce faire, on va aussi ajouter un booléen verbose qui déterminera le niveau de détail qu’on souhaite sur l’exécution :

def run(dfa, word, verbose = False):
    """ Runs the specified DFA on a word and returns True if the word is
        accepted.
        @param dfa      the DFA to be executed.
        @param word     the word to be tested.
        @param verbose  if True, more information are displayed about the
            execution.
        @return True if the word is accepted, False otherwise."""
    if dfa.init == None:
        print("error : the automaton does not have any initial symbol.")
        return False

    current_state = dfa.init

    i = 0
    for symbol in word:
        if verbose : print("configuration : (" + current_state + ", " + word[i:] + ")")
        if not dfa.valid_symbol(symbol):
            print("error : the symbol '" + symbol + "' is not part of the alphabet. Abord.")

        next_state = dfa.dst_state(current_state, symbol)
        if next_state is None:
            if verbose: print("no transition available for (" + current_state + ", " + symbol + ").")
            return False;

        current_state = next_state
        i = i+1

    if current_state in dfa.finals:
        if verbose: print("ending on final state '" + current_state + "'.")
        return True
    if verbose: print("ending on non accepting state '" + current_state + "'")
    return False

def run(dfa, word, verbose = False):

""" Runs the specified DFA on a word and returns True if the word is

accepted.

@param dfa the DFA to be executed.

@param word the word to be tested.

@param verbose if True, more information are displayed about the

execution.

@return True if the word is accepted, False otherwise."""

if dfa.init == None:

print("error : the automaton does not have any initial symbol.")

return False

current_state = dfa.init

i = 0

for symbol in word:

if verbose : print("configuration : (" + current_state + ", " + word[i:] + ")")

if not dfa.valid_symbol(symbol):

print("error : the symbol '" + symbol + "' is not part of the alphabet. Abord.")

next_state = dfa.dst_state(current_state, symbol)

if next_state is None:

if verbose: print("no transition available for (" + current_state + ", " + symbol + ").")

return False;

current_state = next_state

i = i+1

if current_state in dfa.finals:

if verbose: print("ending on final state '" + current_state + "'.")

return True

if verbose: print("ending on non accepting state '" + current_state + "'")

return False

Encore une fois, testons tout ça avec un exemple, en reprenant cette fois l’automate reconnaissant les mots contenant la séquence aaba sur l’alphabet Σ = {a, b} :

~/aumal/src$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17) 
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import DFA
>>> a = DFA.DFA("ab")
>>> 
>>> a.add_state("0")
>>> a.add_state("1")
>>> a.add_state("2")
>>> a.add_state("3")
>>> a.add_state("4", True)
>>> a.init = "0"
>>> 
>>> a.add_transition("0", "a", "1")
>>> a.add_transition("0", "b", "0")
>>> a.add_transition("1", "a", "2")
>>> a.add_transition("1", "b", "0")
>>> a.add_transition("2", "a", "2")
>>> a.add_transition("2", "b", "3")
>>> a.add_transition("3", "a", "4")
>>> a.add_transition("3", "b", "0")
>>> a.add_transition("4", "a", "4")
>>> a.add_transition("4", "b", "4")
>>> 
>>> print(a)
FA :
   - alphabet   : 'ab'
   - init       : 0
   - finals     : ['4']
   - states (5) :
       - (0):
          --(a)--> (1)
          --(b)--> (0)
       - (1):
          --(a)--> (2)
          --(b)--> (0)
       - (2):
          --(a)--> (2)
          --(b)--> (3)
       - (3):
          --(a)--> (4)
          --(b)--> (0)
       - (4):
          --(a)--> (4)
          --(b)--> (4)

>>>

~/aumal/src$ python3

Python 3.6.7 (default, Oct 22 2018, 11:32:17)

[GCC 8.2.0] on linux

Type "help", "copyright", "credits" or "license" for more information.

>>> import DFA

>>> a = DFA.DFA("ab")

>>>

>>> a.add_state("0")

>>> a.add_state("1")

>>> a.add_state("2")

>>> a.add_state("3")

>>> a.add_state("4", True)

>>> a.init = "0"

>>>

>>> a.add_transition("0", "a", "1")

>>> a.add_transition("0", "b", "0")

>>> a.add_transition("1", "a", "2")

>>> a.add_transition("1", "b", "0")

>>> a.add_transition("2", "a", "2")

>>> a.add_transition("2", "b", "3")

>>> a.add_transition("3", "a", "4")

>>> a.add_transition("3", "b", "0")

>>> a.add_transition("4", "a", "4")

>>> a.add_transition("4", "b", "4")

>>>

>>> print(a)

FA :

- alphabet : 'ab'

- init : 0

- finals : ['4']

- states (5) :

- (0):

--(a)--> (1)

--(b)--> (0)

- (1):

--(a)--> (2)

--(b)--> (0)

- (2):

--(a)--> (2)

--(b)--> (3)

- (3):

--(a)--> (4)

--(b)--> (0)

- (4):

--(a)--> (4)

--(b)--> (4)

>>>

Et nous pouvons maintenant tester des séquences :

>>> import algorithms as alg
>>> alg.run(a, "aaba")
True
>>> alg.run(a, "abaa")
False
>>> alg.run(a, "bababa")
False
>>> 
>>> alg.run(a, "aabaabaa", True)
configuration : (0, aabaabaa)
configuration : (1, abaabaa)
configuration : (2, baabaa)
configuration : (3, aabaa)
configuration : (4, abaa)
configuration : (4, baa)
configuration : (4, aa)
configuration : (4, a)
ending on final state '4'.
True
>>> alg.run(a, "bbababaabba", True)
configuration : (0, bbababaabba)
configuration : (0, bababaabba)
configuration : (0, ababaabba)
configuration : (1, babaabba)
configuration : (0, abaabba)
configuration : (1, baabba)
configuration : (0, aabba)
configuration : (1, abba)
configuration : (2, bba)
configuration : (3, ba)
configuration : (0, a)
ending on non accepting state '1'
False
>>>

>>> import algorithms as alg

>>> alg.run(a, "aaba")

True

>>> alg.run(a, "abaa")

False

>>> alg.run(a, "bababa")

False

>>>

>>> alg.run(a, "aabaabaa", True)

configuration : (0, aabaabaa)

configuration : (1, abaabaa)

configuration : (2, baabaa)

configuration : (3, aabaa)

configuration : (4, abaa)

configuration : (4, baa)

configuration : (4, aa)

configuration : (4, a)

ending on final state '4'.

True

>>> alg.run(a, "bbababaabba", True)

configuration : (0, bbababaabba)

configuration : (0, bababaabba)

configuration : (0, ababaabba)

configuration : (1, babaabba)

configuration : (0, abaabba)

configuration : (1, baabba)

configuration : (0, aabba)

configuration : (1, abba)

configuration : (2, bba)

configuration : (3, ba)

configuration : (0, a)

ending on non accepting state '1'

False

>>>

Charger et sauvegarder un automate

Vous l’aurez surement remarqué, le mode interactif est très pratique pour manipuler nos automates et faire des tests, mais devoir recréer l’automate à chaque fois est fastidieux. Il nous faut un moyen de sauvegarder et de charger nos automates pour nous simplifier le travail.

La méthode la plus simple que j’ai trouvé pour ne pas avoir à avoir à définir un format spécifique et à le parser, c’est de simplement enregistrer les lignes de code nécessaires à la recréation de l’automate, puis d’exécuter le fichier contenant ce code et récupérer l’automate correspondant. Ci-suit la fonction de sauvegarde, qu’on mettra dans le fichier util.py :

def save(dfa, filename):
    """ Save the specified dfa into a file.
        A DFA can be read with the 'read' function.
        @param dfa      the DFA to save
        @param filename the name of the file in which
            the automaton will be saved."""
    txt = "a = DFA.DFA(\"" + dfa.alphabet + "\")\n"
    for state in dfa.states:
        if state in dfa.finals:
            txt += "a.add_state(\"" + state + "\", True)\n"
        else:
            txt += "a.add_state(\"" + state + "\")\n"

    txt += "\na.init = \"" + dfa.init + "\"\n\n"

    for state in dfa.states:
        for (symbol, dst_state) in dfa.transitions[state]:
            txt += "a.add_transition(\"" + state + "\", \"" + symbol + "\", \"" + dst_state + "\")\n"

    with open(filename, "w") as file:
        file.write(txt)

def save(dfa, filename):

""" Save the specified dfa into a file.

A DFA can be read with the 'read' function.

@param dfa the DFA to save

@param filename the name of the file in which

the automaton will be saved."""

txt = "a = DFA.DFA(\"" + dfa.alphabet + "\")\n"

for state in dfa.states:

if state in dfa.finals:

txt += "a.add_state(\"" + state + "\", True)\n"

else:

txt += "a.add_state(\"" + state + "\")\n"

txt += "\na.init = \"" + dfa.init + "\"\n\n"

for state in dfa.states:

for (symbol, dst_state) in dfa.transitions[state]:

txt += "a.add_transition(\"" + state + "\", \"" + symbol + "\", \"" + dst_state + "\")\n"

with open(filename, "w") as file:

file.write(txt)

On se contente donc de recréer les commandes qu’on utilise, voyons à quoi ça ressemble avec l’automate précédent :

>>> import util
>>> util.save(a, "../examples/*aaba*.dfa")
>>> exit()
~/aumal/src$ cat ../examples/\*aaba\*.dfa 
a = DFA.DFA("ab")
a.add_state("0")
a.add_state("1")
a.add_state("2")
a.add_state("3")
a.add_state("4", True)

a.init = "0"

a.add_transition("0", "a", "1")
a.add_transition("0", "b", "0")
a.add_transition("1", "a", "2")
a.add_transition("1", "b", "0")
a.add_transition("2", "a", "2")
a.add_transition("2", "b", "3")
a.add_transition("3", "a", "4")
a.add_transition("3", "b", "0")
a.add_transition("4", "a", "4")
a.add_transition("4", "b", "4")
aumal/src$

>>> import util

>>> util.save(a, "../examples/*aaba*.dfa")

>>> exit()

~/aumal/src$ cat ../examples/\*aaba\*.dfa

a = DFA.DFA("ab")

a.add_state("0")

a.add_state("1")

a.add_state("2")

a.add_state("3")

a.add_state("4", True)

a.init = "0"

a.add_transition("0", "a", "1")

a.add_transition("0", "b", "0")

a.add_transition("1", "a", "2")

a.add_transition("1", "b", "0")

a.add_transition("2", "a", "2")

a.add_transition("2", "b", "3")

a.add_transition("3", "a", "4")

a.add_transition("3", "b", "0")

a.add_transition("4", "a", "4")

a.add_transition("4", "b", "4")

aumal/src$

Pour la lecture il nous faut passer par les fonctions compile et exec. exec permet de passer nos variables locales, ce qui va faire que la variable locale a contenant l’automate sera accessible :

def read(filename):
    """ Read the specified dfa from a file.
        A DFA can be saved with the 'save' function.
        @param filename the file in which the DFA is stored.
        @return the DFA from the file.
        """
    local_dict = locals()
    with open(filename, "r") as file:
        exec(compile(open(filename).read(), filename, 'exec'), globals(), local_dict)

    return local_dict["a"]

def read(filename):

""" Read the specified dfa from a file.

A DFA can be saved with the 'save' function.

@param filename the file in which the DFA is stored.

@return the DFA from the file.

"""

local_dict = locals()

with open(filename, "r") as file:

exec(compile(open(filename).read(), filename, 'exec'), globals(), local_dict)

return local_dict["a"]

Et voilà, nous pouvons maintenant sauvegarder et lire nos automates :

~/aumal/src$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17) 
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import DFA
>>> import util
>>> aaba = util.read("../examples/*aaba*.dfa")
>>> print(aaba)
FA :
   - alphabet   : 'ab'
   - init       : 0
   - finals     : ['4']
   - states (5) :
       - (0):
          --(a)--> (1)
          --(b)--> (0)
       - (1):
          --(a)--> (2)
          --(b)--> (0)
       - (2):
          --(a)--> (2)
          --(b)--> (3)
       - (3):
          --(a)--> (4)
          --(b)--> (0)
       - (4):
          --(a)--> (4)
          --(b)--> (4)

>>>

~/aumal/src$ python3

Python 3.6.7 (default, Oct 22 2018, 11:32:17)

[GCC 8.2.0] on linux

Type "help", "copyright", "credits" or "license" for more information.

>>> import DFA

>>> import util

>>> aaba = util.read("../examples/*aaba*.dfa")

>>> print(aaba)

FA :

- alphabet : 'ab'

- init : 0

- finals : ['4']

- states (5) :

- (0):

--(a)--> (1)

--(b)--> (0)

- (1):

--(a)--> (2)

--(b)--> (0)

- (2):

--(a)--> (2)

--(b)--> (3)

- (3):

--(a)--> (4)

--(b)--> (0)

- (4):

--(a)--> (4)

--(b)--> (4)

>>>

Affichage graphique de l’automate

Une dernière question pour cette article : peut-on obtenir une représentation graphique de notre automate ?

L’affichage des graphes de façon correcte est un sujet complexe et c’est très largement hors de la portée de ce cours. En revanche, il existe des outils qui peuvent nous permettre d’y arriver.

Le format DOT est un format texte de représentation de graphes. Il existe des programmes qui génèrent une représentation graphique des fichiers DOT.

Le fichier est relativement simple, il indique le mot-clef digraph, puisque les automates sont des graphes orientés (entendez par là que les transitions ne vont que dans un sens), suivi du nom de l’automate :

digraph mon_automate {
    rankdir="LR";

    // Informations
}

digraph mon_automate {

rankdir="LR";

// Informations

}

rankdir permet de spécifier la direction du graphe. Ici, LR signifie simplement LeftRight, donc de gauche à droite. C’est en général l’orientation la plus naturelle.

Suit ensuite la liste des états, que nous ferons précéder par Q_ de manière à nous assurer que le nom de l’état soit valide pour le format DOT même lorsque c’est un nombre. Le label correspond au nom qui sera affiché :

digraph aaba {
    // States (5)
    Q_0 [label=0];
    Q_1 [label=1];
    Q_2 [label=2];
    Q_3 [label=3];
    Q_4 [label=4];

    // Transitions
    Q_0 -> Q_1 [label=a];
    Q_0 -> Q_0 [label=b];
    Q_1 -> Q_2 [label=a];
    Q_1 -> Q_0 [label=b];
    Q_2 -> Q_2 [label=a];
    Q_2 -> Q_3 [label=b];
    Q_3 -> Q_4 [label=a];
    Q_3 -> Q_0 [label=b];
    Q_4 -> Q_4 [label=a];
    Q_4 -> Q_4 [label=b];
}

digraph aaba {

// States (5)

Q_0 [label=0];

Q_1 [label=1];

Q_2 [label=2];

Q_3 [label=3];

Q_4 [label=4];

// Transitions

Q_0 -> Q_1 [label=a];

Q_0 -> Q_0 [label=b];

Q_1 -> Q_2 [label=a];

Q_1 -> Q_0 [label=b];

Q_2 -> Q_2 [label=a];

Q_2 -> Q_3 [label=b];

Q_3 -> Q_4 [label=a];

Q_3 -> Q_0 [label=b];

Q_4 -> Q_4 [label=a];

Q_4 -> Q_4 [label=b];

}

Pour représenter les états finaux, on va utiliser node [shape=doublecircle]; et node [shape=circle]; qui permettent de définir l’aspect des états ( circle est la valeur par défaut).

Pour l’état initial, on va créer un état supplémentaire dont partira la flèche initial, et lui donner une apparence de point. Voici donc le fichier DOT complet correspondant à notre automate aaba :

digraph aaba {
    rankdir="LR";

    // States (5)
    node [shape = point ];     __Qi__ // Initial state
    node [shape=circle];       Q_0 [label=0];
    node [shape=circle];       Q_1 [label=1];
    node [shape=circle];       Q_2 [label=2];
    node [shape=circle];       Q_3 [label=3];
    node [shape=doublecircle]; Q_4 [label=4];

    // Transitions
    __Qi__ -> Q_0; // Initial state arrow
    Q_0 -> Q_1 [label=a];
    Q_0 -> Q_0 [label=b];
    Q_1 -> Q_2 [label=a];
    Q_1 -> Q_0 [label=b];
    Q_2 -> Q_2 [label=a];
    Q_2 -> Q_3 [label=b];
    Q_3 -> Q_4 [label=a];
    Q_3 -> Q_0 [label=b];
    Q_4 -> Q_4 [label=a];
    Q_4 -> Q_4 [label=b];
}

digraph aaba {

rankdir="LR";

// States (5)

node [shape = point ]; __Qi__ // Initial state

node [shape=circle]; Q_0 [label=0];

node [shape=circle]; Q_1 [label=1];

node [shape=circle]; Q_2 [label=2];

node [shape=circle]; Q_3 [label=3];

node [shape=doublecircle]; Q_4 [label=4];

// Transitions

__Qi__ -> Q_0; // Initial state arrow

Q_0 -> Q_1 [label=a];

Q_0 -> Q_0 [label=b];

Q_1 -> Q_2 [label=a];

Q_1 -> Q_0 [label=b];

Q_2 -> Q_2 [label=a];

Q_2 -> Q_3 [label=b];

Q_3 -> Q_4 [label=a];

Q_3 -> Q_0 [label=b];

Q_4 -> Q_4 [label=a];

Q_4 -> Q_4 [label=b];

}

Un fichier dot peut ensuite être simple transformé en image à l’aide de divers outils, notamment Graphviz. Cette collection d’outils est installée par défaut sur beaucoup de distributions Linux, sinon essayez de trouver le paquet correspondant ( apt install graphviz). Pour créer une image PNG à partir du fichier DOT : dot -Tpng *aaba*.dot -o *aaba*.png. Ci-suit l’image résultant de cette commande :

Le résultat est tout à fait convainquant, je vous propose donc d’ajouter ces fonctionnalités d’exportation en DOT, en PNG et en PDF directement dans le fichier util.py, en utilisant le module subprocess pour exécuter les appels à dot :

def to_dot(dfa, name="Graph"):
    """ Returns a string corresponding to the specified DFA in DOT format.
        @param dfa  the DFA to be converted in DOT format.
        @param name the name of the automaton for the DOT file ("Graph")
            by default.
        @returns the automaton in DOT format."""
    ret = "digraph " + name + " {\n    rankdir=\"LR\";\n\n"
    ret += "    // States (" + str(len(dfa.states)) + ")\n"

    state_name = lambda s : "Q_" + str(dfa.states.index(s))

    # States
    ret += "    node [shape = point ];     __Qi__ // Initial state\n" # Initial state
    for state in dfa.states:
        ret += "    "
        if state in dfa.finals:
            ret += "node [shape=doublecircle]; "
        else:
            ret += "node [shape=circle];       "
        ret += state_name(state) + " [label=" + state + "];\n"

    # Transitions
    ret += "\n    // Transitions\n"
    ret += "    __Qi__ -> " + state_name(dfa.init) + "; // Initial state arrow\n"
    for state in dfa.states:
        for (symbol, dst_state) in dfa.transitions[state]:
            ret += "    " + state_name(state) + " -> " + state_name(dst_state) + " [label=" + symbol + "];\n"
    return ret + "}\n"

def to_png(dfa, filename=None, name="Graph"):
    """ Create the PNG image corresponding to the representation of the
        specified DFA in a file.
        The automaton is converted in DOT format and the command dot is called
        in order to generate the PNG.
        @param dfa      the DFA to be converted in PNG.
        @param name     the name of the graph.
        @param filename the name of the PNG file, use the name of the graph if
            not specified. """

    if filename is None:
        filename = name + ".png"

    tmp_file = filename + ".tmp"
    with open(tmp_file, "w") as file:
        file.write(to_dot(dfa, name))

    call(("dot -Tpng " + tmp_file + " -o " + filename).split(" "))
    call(("rm " + tmp_file).split(" "))


def to_pdf(dfa, filename=None, name="Graph"):
    """ Create the graphical PDF representation of the specified DFA in a file.
        The automaton is converted in DOT format and the command dot is called
        in order to generate the PDF.
        @param dfa      the DFA to be converted in PDF.
        @param name     the name of the graph.
        @param filename the name of the PDF file, use the name of the graph if
            not specified. """

    if filename is None:
        filename = name + ".pdf"

    tmp_file = filename + ".tmp"
    with open(tmp_file, "w") as file:
        file.write(to_dot(dfa, name))

    call(("dot -Tpdf " + tmp_file + " -o " + filename).split(" "))
    call(("rm " + tmp_file).split(" "))

def to_dot(dfa, name="Graph"):

""" Returns a string corresponding to the specified DFA in DOT format.

@param dfa the DFA to be converted in DOT format.

@param name the name of the automaton for the DOT file ("Graph")

by default.

@returns the automaton in DOT format."""

ret = "digraph " + name + " {\n rankdir=\"LR\";\n\n"

ret += " // States (" + str(len(dfa.states)) + ")\n"

state_name = lambda s : "Q_" + str(dfa.states.index(s))

# States

ret += " node [shape = point ]; __Qi__ // Initial state\n" # Initial state

for state in dfa.states:

ret += " "

if state in dfa.finals:

ret += "node [shape=doublecircle]; "

else:

ret += "node [shape=circle]; "

ret += state_name(state) + " [label=" + state + "];\n"

# Transitions

ret += "\n // Transitions\n"

ret += " __Qi__ -> " + state_name(dfa.init) + "; // Initial state arrow\n"

for state in dfa.states:

for (symbol, dst_state) in dfa.transitions[state]:

ret += " " + state_name(state) + " -> " + state_name(dst_state) + " [label=" + symbol + "];\n"

return ret + "}\n"

def to_png(dfa, filename=None, name="Graph"):

""" Create the PNG image corresponding to the representation of the

specified DFA in a file.

The automaton is converted in DOT format and the command dot is called

in order to generate the PNG.

@param dfa the DFA to be converted in PNG.

@param name the name of the graph.

@param filename the name of the PNG file, use the name of the graph if

not specified. """

if filename is None:

filename = name + ".png"

tmp_file = filename + ".tmp"

with open(tmp_file, "w") as file:

file.write(to_dot(dfa, name))

call(("dot -Tpng " + tmp_file + " -o " + filename).split(" "))

call(("rm " + tmp_file).split(" "))

def to_pdf(dfa, filename=None, name="Graph"):

""" Create the graphical PDF representation of the specified DFA in a file.

The automaton is converted in DOT format and the command dot is called

in order to generate the PDF.

@param dfa the DFA to be converted in PDF.

@param name the name of the graph.

@param filename the name of the PDF file, use the name of the graph if

not specified. """

if filename is None:

filename = name + ".pdf"

tmp_file = filename + ".tmp"

with open(tmp_file, "w") as file:

file.write(to_dot(dfa, name))

call(("dot -Tpdf " + tmp_file + " -o " + filename).split(" "))

call(("rm " + tmp_file).split(" "))

Voici un exemple d’utilisation :

aumal/src$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17) 
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import DFA
>>> import util
>>> a = util.read("../examples/*aaba*.dfa")
>>> util.to_dot(a)
'digraph Graph {\n    rankdir="LR";\n\n    // States (5)\n    node [shape = point ];     __Qi__ // Initial state\n    node [shape=circle];       Q_0 [label=0];\n    node [shape=circle];       Q_1 [label=1];\n    node [shape=circle];       Q_2 [label=2];\n    node [shape=circle];       Q_3 [label=3];\n    node [shape=doublecircle]; Q_4 [label=4];\n\n    // Transitions\n    __Qi__ -> Q_0; // Initial state arrow\n    Q_0 -> Q_1 [label=a];\n    Q_0 -> Q_0 [label=b];\n    Q_1 -> Q_2 [label=a];\n    Q_1 -> Q_0 [label=b];\n    Q_2 -> Q_2 [label=a];\n    Q_2 -> Q_3 [label=b];\n    Q_3 -> Q_4 [label=a];\n    Q_3 -> Q_0 [label=b];\n    Q_4 -> Q_4 [label=a];\n    Q_4 -> Q_4 [label=b];\n}\n'
>>> util.to_pdf(a, "../examples/*aaba*.pdf")
Error: ../examples/*aaba*.pdf.tmp: syntax error in line 1 near 'Graph'
>>> util.to_pdf(a, "../examples/*aaba*.pdf", "aaba")
>>>

aumal/src$ python3

Python 3.6.7 (default, Oct 22 2018, 11:32:17)

[GCC 8.2.0] on linux

Type "help", "copyright", "credits" or "license" for more information.

>>> import DFA

>>> import util

>>> a = util.read("../examples/*aaba*.dfa")

>>> util.to_dot(a)

'digraph Graph {\n rankdir="LR";\n\n // States (5)\n node [shape = point ]; __Qi__ // Initial state\n node [shape=circle]; Q_0 [label=0];\n node [shape=circle]; Q_1 [label=1];\n node [shape=circle]; Q_2 [label=2];\n node [shape=circle]; Q_3 [label=3];\n node [shape=doublecircle]; Q_4 [label=4];\n\n // Transitions\n __Qi__ -> Q_0; // Initial state arrow\n Q_0 -> Q_1 [label=a];\n Q_0 -> Q_0 [label=b];\n Q_1 -> Q_2 [label=a];\n Q_1 -> Q_0 [label=b];\n Q_2 -> Q_2 [label=a];\n Q_2 -> Q_3 [label=b];\n Q_3 -> Q_4 [label=a];\n Q_3 -> Q_0 [label=b];\n Q_4 -> Q_4 [label=a];\n Q_4 -> Q_4 [label=b];\n}\n'

>>> util.to_pdf(a, "../examples/*aaba*.pdf")

Error: ../examples/*aaba*.pdf.tmp: syntax error in line 1 near 'Graph'

>>> util.to_pdf(a, "../examples/*aaba*.pdf", "aaba")

>>>

Voilà donc qui conclut cet article sur l’implémentation de nos automates finis déterministes. A cette adresse, vous trouverez la version complète du projet à l’issu de cet article, qui contient quelques automates d’exemple.

Je vous dis donc à une prochaine fois pour un nouvel article !

Implémentation d’un AFD en Python

Avant de commencer

Modélisation d’un automate

L’implémentation

Exécution d’un automate

Charger et sauvegarder un automate

Affichage graphique de l’automate

Like this:

Articles similaires

Avant de commencer

Modélisation d’un automate

L’implémentation

Exécution d’un automate

Charger et sauvegarder un automate

Affichage graphique de l’automate

Partager :

Like this:

Articles similaires