Les notebooks du répertoire documents sont maintenant en lecture seule :

  • Vous pouvez tester/exécuter le code comme vous voulez (Shift-Entrée ou Ctrl-Entrée)
  • Mais vous ne pouvez pas enregistrer directement : utilisez le menu Fichier > Créer une copie... pour créer une copie du notebook dans votre répertoire (mais pas dans documents).
  • Rappel : si Python/Ocaml "plante" : menu Noyau > Redémarer
  • En général, pensez à évaluer la ou les premières cellules (modules, types, définitions pratiques...) : sinon vous aurez des erreurs (... not defined, unbound value ...)

N'hésitez pas à me poser des questions en cas de problème !

In [1]:
from automates import Automate

def afficher(automate):
    import graphviz # pas à connaître du tout pour les concours ;-)
    alpha, etats, I, F, delta = automate
    s = ["digraph Automate {", "rankdir=LR", "node[shape=circle]"]
    for e in etats:
        if e in I:
            s.append('"start_{}" [style=invis]'.format(e))
            s.append('"start_{}" -> "{}"'.format(e, e))
        s.append('"{}" [label="{}"{}]'.format(e, e, " penwidth=4" if e in F else ""))
    for depart, lettre, arrivee in delta:
        s.append('"{}" -> "{}" [label="{}"]'.format(depart, arrivee, lettre))
    s.append("}")
    return graphviz.Source('\n'.join(s), engine='dot')
In [2]:
def union_listes(u, v):
    return sorted(set(u)|set(v))

def intersection_listes(u, v):
    return sorted(set(u)&set(v))

def unique_liste(liste):
    return sorted(set(liste))

Glushkov

In [3]:
A = Automate.glushkov("(ab(ab)*)*+(ba)*").export()  # Wikipedia
B = Automate.glushkov("a(a+b)*a+b(a+b)*b").export() # Mines 2011
C = Automate.glushkov("a*bc*").export()
D = Automate.glushkov("aa*a").export()
In [4]:
A   # (alphabet, états, états_initiaux, états_finaux, transitions)
Out[4]:
(['a', 'b'],
 ['0', 'a_0', 'a_2', 'a_5', 'b_1', 'b_3', 'b_4'],
 ['0'],
 ['a_5', 'b_1', 'b_3'],
 [('0', 'a', 'a_0'),
  ('0', 'b', 'b_4'),
  ('a_0', 'b', 'b_1'),
  ('a_2', 'b', 'b_3'),
  ('a_5', 'b', 'b_4'),
  ('b_1', 'a', 'a_0'),
  ('b_1', 'a', 'a_2'),
  ('b_3', 'a', 'a_0'),
  ('b_3', 'a', 'a_2'),
  ('b_4', 'a', 'a_5')])

Expression régulière linéarisée / marquage : $(a_0b_1(a_2b_3)*)*+(b_4a_5)*$

In [5]:
afficher(A)
Out[5]:
Automate 0 0 start_0->0 a_0 a_0 0->a_0 a b_4 b_4 0->b_4 b b_1 b_1 a_0->b_1 b a_2 a_2 b_3 b_3 a_2->b_3 b a_5 a_5 a_5->b_4 b b_1->a_0 a b_1->a_2 a b_3->a_0 a b_3->a_2 a b_4->a_5 a

Transition / Reconnaître

In [6]:
def transition(automate, etats_depart, lettre):
    """ On passe d'un ensemble d'états dans un ensemble d'états """
    _, etats, _, _, delta = automate
    assert all([e in etats for e in etats_depart]), ("État de départ inconnu : ", etats_depart, etats)
    return unique_liste([y for (x, l, y) in delta for e in etats_depart if x==e and l==lettre])
In [7]:
transition(A, ['0', 'a_0', 'b_1'], 'a')
Out[7]:
['a_0', 'a_2']
In [8]:
def reconnaitre(automate, mot):
    _, _, I, F, delta = automate
    etats = I
    for lettre in mot:
        etats = transition(automate, etats, lettre)
    return intersection_listes(etats, F) != []
In [9]:
reconnaitre(A, "abab"), reconnaitre(A, "ababb")
Out[9]:
(True, False)

Renommer

In [10]:
def renommer(automate, prefixe=""):
    alpha, etats, I, F, delta = automate
    t = {}
    for i, e in enumerate(etats):
        t[str(e)] = prefixe+str(i)
    return ([a for a in alpha],
            [t[str(e)] for e in etats],
            [t[str(e)] for e in I],
            [t[str(e)] for e in F],
            [(t[str(a)], l, t[str(b)]) for a, l, b in delta],
           )
In [11]:
A_ok = renommer(A)
afficher(A_ok)
Out[11]:
Automate 0 0 start_0->0 1 1 0->1 a 6 6 0->6 b 4 4 1->4 b 2 2 5 5 2->5 b 3 3 3->6 b 4->1 a 4->2 a 5->1 a 5->2 a 6->3 a
In [12]:
C_ok = renommer(C)
afficher(C_ok)
Out[12]:
Automate 0 0 start_0->0 1 1 0->1 a 2 2 0->2 b 1->1 a 1->2 b 3 3 2->3 c 3->3 c

Union

  • Tout simplement des 2 automates "côte à côte"
  • On pourrait aussi utiliser un automate produit en modifiant les états finaux
In [13]:
def union(A, B):
    if intersection_listes(A[1], B[1]) != []:
        A, B = renommer(A, "p"), renommer(B, "q")
    assert intersection_listes(A[1], B[1]) == [], "Les états doivent être disjoints"
    alphaA, etatsA, IA, FA, deltaA = A
    alphaB, etatsB, IB, FB, deltaB = B
    return (union_listes(alphaA, alphaB), etatsA+etatsB, IA+IB, FA+FB, deltaA+deltaB)
In [14]:
afficher(union(A, C))  # Ici, on obtient *un* automate non déterministe
Out[14]:
Automate p0 p0 start_p0->p0 p1 p1 p0->p1 a p6 p6 p0->p6 b p4 p4 p1->p4 b p2 p2 p5 p5 p2->p5 b p3 p3 p3->p6 b p4->p1 a p4->p2 a p5->p1 a p5->p2 a p6->p3 a q0 q0 start_q0->q0 q1 q1 q0->q1 a q2 q2 q0->q2 b q1->q1 a q1->q2 b q3 q3 q2->q3 c q3->q3 c
In [15]:
nondeterministe = renommer(union(A, C))
afficher(nondeterministe)
Out[15]:
Automate 0 0 start_0->0 1 1 0->1 a 6 6 0->6 b 4 4 1->4 b 2 2 5 5 2->5 b 3 3 3->6 b 4->1 a 4->2 a 5->1 a 5->2 a 6->3 a 7 7 start_7->7 8 8 7->8 a 9 9 7->9 b 8->8 a 8->9 b 10 10 9->10 c 10->10 c

Déterminiser - Automate des parties

In [16]:
def determiniser(A):
    alphaA, etatsA, IA, FA, deltaA = A
    alpha = alphaA[:]
    etats, I, F, delta = [], [], [], []
    I.append(IA)                    # Le (seul) nouvel état initial est l'ensemble des états initiaux de A
    suivants = [IA]                 # parcours de graphe classique. Ici "vu" correspond à 'etats'
    while suivants != []:
        super_etat = suivants.pop() # chaque nouveau super_etat est une *partie* : ici une liste
        if super_etat not in etats:
            etats.append(super_etat)
            if any(e in FA for e in super_etat):
                F.append(super_etat)
            for lettre in alpha:
                arrivee = transition(A, super_etat, lettre) # automate de départ
                delta.append((super_etat, lettre, arrivee))
                suivants.append(arrivee)
    return (alpha, etats, I, F, delta)
In [17]:
A_det = determiniser(A_ok)
afficher(A_det)
Out[17]:
Automate ['0'] ['0'] start_['0']->['0'] ['6'] ['6'] ['0']->['6'] b ['1'] ['1'] ['0']->['1'] a [] [] ['6']->[] b ['3'] ['3'] ['6']->['3'] a []->[] a []->[] b ['3']->['6'] b ['3']->[] a ['1']->[] a ['4'] ['4'] ['1']->['4'] b ['4']->[] b ['1', '2'] ['1', '2'] ['4']->['1', '2'] a ['1', '2']->[] a ['4', '5'] ['4', '5'] ['1', '2']->['4', '5'] b ['4', '5']->[] b ['4', '5']->['1', '2'] a
In [18]:
afficher(A_ok)
Out[18]:
Automate 0 0 start_0->0 1 1 0->1 a 6 6 0->6 b 4 4 1->4 b 2 2 5 5 2->5 b 3 3 3->6 b 4->1 a 4->2 a 5->1 a 5->2 a 6->3 a
In [19]:
A_det = renommer(A_det)
afficher(A_det)
Out[19]:
Automate 0 0 start_0->0 1 1 0->1 b 4 4 0->4 a 2 2 1->2 b 3 3 1->3 a 2->2 a 2->2 b 3->1 b 3->2 a 4->2 a 5 5 4->5 b 5->2 b 6 6 5->6 a 6->2 a 7 7 6->7 b 7->2 b 7->6 a

Émonder

On ne veut garder que les états à la fois accessibles (depuis un état initial) et coaccessibles (à partir desquels on peut accéder à un état final)

In [20]:
def emonder(A):
    alphaA, etatsA, IA, FA, deltaA = A
       
    accessibles = []
    suivants = IA[:] # on fait une copie pour ne pas modifier IA
    while suivants != []:
        etat = suivants.pop()
        if etat not in accessibles: # C'est un parcours de graphe. `accessible` a le rôle de `vu`
            accessibles.append(etat)
            suivants.extend(unique_liste([y for x, _, y in deltaA if x==etat]))
            
    coaccessibles = []
    suivants = FA[:]
    while suivants != []:
        etat = suivants.pop()
        if etat not in coaccessibles:
            coaccessibles.append(etat)
            suivants.extend(unique_liste([x for x, _, y in deltaA if y==etat]))
            
    etats = intersection_listes(accessibles, coaccessibles)
    delta = [(x, l, y) for (x, l, y) in deltaA if x in etats and y in etats]
    return (alphaA[:], etats, intersection_listes(IA, etats), intersection_listes(FA, etats), delta)
In [21]:
A_em = emonder(A_det)
afficher(A_em)
Out[21]:
Automate 0 0 start_0->0 1 1 0->1 b 4 4 0->4 a 3 3 1->3 a 3->1 b 5 5 4->5 b 6 6 5->6 a 7 7 6->7 b 7->6 a
In [22]:
afficher(A_ok) # Non déterministe
Out[22]:
Automate 0 0 start_0->0 1 1 0->1 a 6 6 0->6 b 4 4 1->4 b 2 2 5 5 2->5 b 3 3 3->6 b 4->1 a 4->2 a 5->1 a 5->2 a 6->3 a

Générer

  • On fait un parcours en largeur : on considère d'abord tous les mots de longueur 0, puis 1, puis 2, ...
    • Le graphe considéré n'existe pas vraiment : on le génère au fur et à mesure du parcours
    • Sommets : (etats, mot) où etats ets l'ensemble des états accessibles en lisant mot
    • Pour l'alphabet ["a", "b"], on condière d'abord le sommet correspondant au mot "", puis "a", "b", "aa", "ab", "ba", "bb", "aaa", "aab"...
  • Pas en profondeur sinon on testerai d'abord tous les mots de la forme $a^k, k \in \mathbb{N}$...
In [23]:
def generer(automate, taille):
    alpha, etats, I, F, delta = automate
    mots = []
    suivants = [(I, "")]     # éléments : (ensemble d'état, mot lu)
    while not (suivants==[] or len(mots)>=taille):
        etats, mot = suivants.pop(0) # Parcours en largeur
        if intersection_listes(etats, F) != []:
            mots.append(mot)
        for lettre in alpha:
            suivants.append((transition(automate, etats, lettre), mot+lettre))
    return mots
In [24]:
n = 8
generer(A, n), generer(A_det, n), generer(B, n), generer(C, n), generer(D, n),
Out[24]:
(['ab', 'ba', 'abab', 'baba', 'ababab', 'bababa', 'abababab', 'babababa'],
 ['ab', 'ba', 'abab', 'baba', 'ababab', 'bababa', 'abababab', 'babababa'],
 ['aa', 'bb', 'aaa', 'aba', 'bab', 'bbb', 'aaaa', 'aaba'],
 ['b', 'ab', 'bc', 'aab', 'abc', 'bcc', 'aaab', 'aabc'],
 ['aa', 'aaa', 'aaaa', 'aaaaa', 'aaaaaa', 'aaaaaaa', 'aaaaaaaa', 'aaaaaaaaa'])
In [25]:
def generer_mieux(automate, taille):
    alpha, etats, I, F, delta = emonder(automate)
    mots = []
    suivants = [(I, "")]     # éléments : (ensemble d'état, mot lu)
    while not (suivants==[] or len(mots)>=taille):
        etats, mot = suivants.pop(0) # Parcours en largeur
        if intersection_listes(etats, F) != []:
            mots.append(mot)
        for lettre in alpha:
            nouveaux_etats = transition(automate, etats, lettre)
            if nouveaux_etats != []:
                suivants.append((nouveaux_etats, mot+lettre))
    return mots
In [26]:
E = Automate.glushkov("abcdefgh+(aaa)*").export()
generer_mieux(E, 30)
Out[26]:
['aaa',
 'aaaaaa',
 'abcdefgh',
 'aaaaaaaaa',
 'aaaaaaaaaaaa',
 'aaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa']
In [27]:
generer(E, 2)
Out[27]:
['aaa', 'aaaaaa']

Complet

In [28]:
def complet(A):
    alpha, etats, I, F, delta = (x[:] for x in A)
    existants = [(x, l) for (x, l, _) in delta]
    non_existants = [(e, a) for e in etats for a in alpha if (e, a) not in existants]
    if non_existants != []: # l'automate n'est pas complet
        puits = "p"
        if puits in etats:
            i = 0
            while "p"+str(i) in etats:
                i+=1
            puits = 'p'+str(i)
        etats.append(puits)
        for e, a in non_existants: # transitions manquantes
            delta.append((e, a, puits))
        for a in alpha:            # boucles sur le puits
            delta.append((puits, a, puits))
    return (alpha, etats, I, F, delta)
In [29]:
afficher(complet(complet(A_ok)))
Out[29]:
Automate 0 0 start_0->0 1 1 0->1 a 6 6 0->6 b 4 4 1->4 b p p 1->p a 2 2 5 5 2->5 b 2->p a 3 3 3->6 b 3->p a 4->1 a 4->2 a 4->p b 5->1 a 5->2 a 5->p b 6->3 a 6->p b p->p a p->p b

Automate Standarid

In [30]:
# TODO

Automate produit : Intersection

  • Automate des parties
In [31]:
# TODO

Shuffle

In [32]:
# TODO

$\frac{1}{2}.L$

In [33]:
# TODO

$\sqrt{L}$

In [34]:
# TODO

Miroir

In [35]:
# TODO

Minimiser

In [36]:
# TODO

Automates et Floyd-Warshall

In [37]:
# TODO