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