automate_n1.py

Created by schraf

Created on October 24, 2022

492 Bytes

But de nos automates: Reconnaitre un langage

Alphabet Σ : par exemple constitué de 2 lettres {a, b}
Mots créés à partir de l’alphabet Σ : par exemples aaa, ababab, bbaaa, etc.
Un automate va être un ensemble d’états (cercles) et de transitions (flèches)
Un état initial (pour nous il n’y en aura qu’un seul et ce sera toujours le cercle de numéro “0”) et un ou plusieurs états finaux (cercles doubles)
Un mot est accepté lorsque l’on arrive dans un état final sinon il est rejeté.

Automate n°1

Cet automate accepte-t-il le mot “ba” ? Réponse : NON, car en partant de l’état 0, la lettre “b” nous amène au cercle 1 puis le “a” nous ramène à l’état 0. Or cet état n’est pas un état final (pas de cercle double comme pour le 1). Donc le mot est refusé.
Cet automate accepte-t-il le mot “abbb” ? Réponse : OUI, le “a” nous amène au cercle 1 puis on y reste avec les 3 “b”.
Intuitivement, quels mots reconnait cet automate ? Réponse : Que l’on soit en 0 ou en 1, la lettre “a” nous ramène en 0. Pour arriver en 1 il faudra donc que la dernière lettre soit obligatoirement un “b”. Inversement, il suffit que le mot se termine par un “b” pour arriver à l’état final 1. Cet automate reconnait tous les mots (écrits avec l’alphabet Σ = {a, b} qui se terminent par “b”)

Automate n°2

Il ressemble beaucoup au précédent mais il ne reconnait pas du tout le même langage !

Cet automate accepte-t-il le mot “ba” ? Réponse : OUI
Cet automate accepte-t-il le mot “aa” ? Réponse : NON
Cet automate accepte-t-il le mot “abbaabb” ? Réponse : OUI
Intuitivement, quels mots reconnait cet automate ? Réponse : Les mots qui contiennent un nombre impair de “a”

On re

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

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

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

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