Automates
TBD https://www.youtube.com/watch?v=DiXMoBMWMmA TBD https://www.youtube.com/watch?v=5vbk0TwkokM
Une classe de langages particulier, décidables, sont très utiles, c'est ceux que l'on peut créer avec un automate (fini) :
Définition
Un automate est un décideur admettant comme entrée les mots d'un alphabet $\mathcal{A}$.
Il est défini grace à une fonction de transition $f: \mathcal{A} \times Q \rightarrow Q$, où $Q$ est un ensemble fini d'états et deux paramètres :
- $q_0 \in Q$ l'état initial
- $F \subseteq Q$ les états d'acceptation
Son algorithme est entièrement défini par eux :
# avec f, q0 et F définis
def automate(m):
q= q0
for a in m:
q = f(a, q)
return q in F Un automate est une version simplifiée d'une machine de Turing (donc d'un algorithme), il n'y a pas de possibilité de stocker des variables, et sa forme est déterminée exclusivement par sa fonction de transition. On a alors coutume de représenter les automates par un diagramme :
TBD exemple. avec départ et arrivées. TBD cours https://pageperso.lis-lab.fr/arnaud.labourel/AUTO/cours7.pdf
Les langages reconnaissables par un automates sont strictement inclus dans les langages décidables :
Définition
Un langage est dit rationnel s'il existe un automate pour le reconnaître.
De nombreux langages sont rationnels :
- constante
- tbd exemples
tbd rationnels
tbd pas tout : palindrome marche pas. On est que à un endroit de la chaine alors que palindrome demaine d'être à deux endroit à la fois (début et fin).
exercices classiques
c'est une expression régulière. def, ref et conversion des exercices en expressions
dire que c'est super utile pour rechercher des motifs dans un texte (numéro de tel, un réel, etc)
imlémentation d'un moteur d'expression reg compliqué. On va s'intéresser à un cas particulier. retrouver un sous-mot dans une chaine
Autres Automate
non déterministe = déterministe. Important car expression reg
.*ab.*par exemple est très facile à écrire en non déterministe.
on peu ajouter du stockage automate à pile, mais toujours pas tout. expression reg avec des
$1
TBD (on appelle cela des expression régulières)
La formalisation et l'étude des expressions régulières dépassent le cadre de ce cours introductif mais c'est un sujet à la fois marrant, utile et intéressant. Si vous voulez vous initier en douceur, lisez le tuto python qui y est consacré, ou passez directement à O'reilly.
TBD
- https://pressbooks.senecapolytechnic.ca/uli101/chapter/extended-regular-expressions/
- https://docs.python.org/fr/3.13/library/re.html
- https://github.com/gawron/python-for-social-science/blob/master/text_classification/regular_expressions.ipynb
- https://cs.uwaterloo.ca/~dtompkin/teaching/08a/lab7/
Pour aller plus loin : grammaires, parseur de langages et automates à pile