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 passe dans l'état 2 et on lit le caractère suivant,
dans l'état 2, si le caractère lu est un "a", on reste dans l'état 2 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.
Afin de tester si un mot correspond à l'expression régulière représentée par un automate, vous pourrez utiliser la fonction correspond qui prend en paramètres :
mot, un texte correspondant au texte à vérifier ;
automate, un dictionnaire correspondant à un automate ;
debut, un entier correspondant à l'état initial de l'automate ;
fin, un entier correspondant à l'état final de l'automate.
Exemple avec l'automate de l'énoncé
Vous pouvez tester différents mots avec l'automate de l'exemple et la fonction correspond.
Cet automate reconnaît "bato" et "baato" mais pas "bota" (exemple du sujet) :
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Question 1
Cet automate reconnaît "tada" et "tadaaa" mais pas "tad" ni "taada" :
Compléter la définition de cet automate ci-dessous.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)