automate_n2.py

Created by schraf

Created on September 10, 2018

514 Bytes

Il faut avoir fait l’activité automate_n1.py avant de regarder celle-ci.

Automate n°2 de l'activité n°1

Imaginons que l’alphabet de cet automate soit beaucoup plus grand (par exemple Σ correspond à toutes les lettres de l’alphabet). Dans ce cas il devient quasi impossible de dessiner toutes les flèches. Ce que nous voulons est donc ( Σ - a signifie “Toutes les lettres sauf le “a”)

Pour cela nous allons tout simplement renseigner uniquement les transitions qui sont utiles et oublier toutes les autres (celles qui font rester sur place).
Finalement, l’automate ci-dessus se réduit à a2 = [{"a":1},{"a":0}]

Comment s’écrit la version simplifiée de l’automate n°1 de l’activité 1 ?

Réécrire les 2 fonctions accepte et details de l’activité n°1 pour qu’elles acceptent ces automates simplifiés en paramètres.

a1 = [{"b":1},{"a":0}]
f1 = [1]

a2 = [{"a":1},{"a":0}]
f2 = [1]

def accepte(mot,a,f):
    e = 0
    for c in mot:
      if c in a[e]:
        e = a[e][c]
    return e in f
        
# accepte("club",a1,f1) donne True 
# accepte("ananas",a2,f2) donne True

def details(mot,a,f):
    e = 0
    for c in mot:
      print("Etat "+ str(e))
      if c in a[e]:
        e = a[e][c]
      print("Lettre "+c+" >")
    if e in f:
      return str(e)+ " = etat final"
    return str(e)+" = pas final"