Automate en dictionnaire
Une expression régulière est une chaine de caractères permettant de décrire d'autres chaines de caractères.
Par exemple, la chaine "ba+to+"
permet de décrire les « mots » "bato"
, "baato"
, "batoo"
et "baatooooo"
: un caractère "b"
suivi d'au moins un caractère "a"
, puis un "t"
et enfin un ou plusieurs caractères "o"
.
Les expressions régulières peuvent être aussi représentées sous forme d'automates. Ainsi, la chaine "ba+to+"
est équivalente à l'automate ci-dessous :
Dans ce graphe, chaque nœud représente un « état » de l'automate. L'état 0 est l'état de début et 4 celui de fin.
On parcourt l'automate de la façon suivante :
- on débute dans l'état de départ en lisant le premier caractère de la chaine,
- si ce caractère est un
"b"
, on passe dans l'état 1 et on lit le caractère suivant, - dans l'état 1, si le caractère lu est un
"a"
, on reste dans l'état 1 et on lit le caractère suivant, - etc
Si on se trouve dans l'état final après avoir lu le dernier caractère de la chaine, alors celle-ci correspond au motif cherché.
La chaine "baato"
est reconnue car elle correspond au parcours 0 → 1 → 2 → 2 → 3 → 4.
On représente un automate par une série de règles stockées dans un dictionnaire Python. Chaque règle associe à un couple (état, caractère lu)
la valeur du prochain état.
Ainsi l'automate ci-dessus est représenté par le dictionnaire automate_0 = {(0, "b"): 1, (1, "a"): 2, (2, "a"): 2, (2, "t"): 3, (3, "o"): 4, (4, "o"): 4}
. L'état initial est le 0
, le final 4
.
On demande d'écrire les dictionnaires représentant les automates suivants. On identifiera aussi les états de départ et de fin.
Cet automate reconnaît "bato"
et "baato"
mais pas "bota" (exemple du sujet) :
Cet automate reconnaît "tada"
et "tadaaa"
mais pas "tad"
ni "taada"
:
Cet automate reconnaît "ruche"
et "riche"
mais pas "reche"
ni "rche"
:
Cet automate reconnaît "vroum"
, "broum"
et "vrououm"
mais pas "brou"
ni "vrouom"
.
# Cet automate reconnaît "bato" et "baato" mais pas "bota" (exemple du sujet)bksl-nlautomatepy-und0 = {(0, "b"): 1, (1, "a"): 2, (2, "a"): 2, (2, "t"): 3, (3, "o"): 4, (4, "o"): 4}bksl-nldebutpy-und0 = 0bksl-nlfinpy-und0 = 4bksl-nlbksl-nl# Cet automate reconnaît "tada" et "tadaaa" mais pas "tad" ni "taada"bksl-nlautomatepy-und1 = ...bksl-nldebutpy-und1 = ...bksl-nlfinpy-und1 = ...bksl-nlbksl-nl# Cet automate reconnaît "ruche" et "riche" mais pas "reche" ni "rche"bksl-nlautomatepy-und2 = ...bksl-nldebutpy-und2 = ...bksl-nlfinpy-und2 = ...bksl-nlbksl-nl# Cet automate reconnaît "vroum"
, "broum"
et "vrououm"
mais pas "brou"
ni "vrouom"
bksl-nlautomatepy-und3 = ...bksl-nldebutpy-und3 = ...bksl-nlfinpy-und3 = ...bksl-nlbksl-nl# Cet automate reconnaît "bato" et "baato" mais pas "bota" (exemple du sujet)bksl-nlautomatepy-und0 = {bksl-nl (0, "b"): 1,bksl-nl (1, "a"): 2,bksl-nl (2, "a"): 2,bksl-nl (2, "t"): 3,bksl-nl (3, "o"): 4,bksl-nl (4, "o"): 4,bksl-nl}bksl-nldebutpy-und0 = 0bksl-nlfinpy-und0 = 4bksl-nlbksl-nl# Cet automate reconnaît "tada" et "tadaaa" mais pas "tad" ni "taada"bksl-nlautomatepy-und1 = {(0, "t"): 1, (1, "a"): 2, (2, "d"): 3, (3, "a"): 4, (4, "a"): 4}bksl-nldebutpy-und1 = 0bksl-nlfinpy-und1 = 4bksl-nlbksl-nl# Cet automate reconnaît "ruche" et "riche" mais pas "reche" ni "rche"bksl-nlautomatepy-und2 = {bksl-nl (0, "r"): 1,bksl-nl (1, "u"): 2,bksl-nl (2, "c"): 4,bksl-nl (1, "i"): 3,bksl-nl (3, "c"): 4,bksl-nl (4, "h"): 5,bksl-nl (5, "e"): 6,bksl-nl}bksl-nldebutpy-und2 = 0bksl-nlfinpy-und2 = 6bksl-nlbksl-nl# Cet automate reconnaît "vroum"
, "broum"
et "vrououm"
mais pas "brou"
ni "vrouom"
bksl-nlautomatepy-und3 = {bksl-nl (0, "v"): 1,bksl-nl (0, "b"): 2,bksl-nl (1, "r"): 3,bksl-nl (2, "r"): 3,bksl-nl (3, "o"): 4,bksl-nl (4, "u"): 5,bksl-nl (5, "o"): 4,bksl-nl (5, "m"): 6,bksl-nl}bksl-nldebutpy-und3 = 0bksl-nlfinpy-und3 = 6bksl-nlbksl-nl
A
Pas de remarques particulières.
Z