|
Outils logiciels pour les cours Paris II
Cours Paris II
Stages/ Thèses/ Séminaires |
BI 2
Notation pour un sous-ensemble de mots. Soit A l'alphabet, par exemple A={a,b}. Tout mot est une expression régulière. Si r1 et r2 sont deux expressions régulières alors r1.r2 , r1 +r2 et (r1)* sont des expressions régulières. Le langage dénoté par r1.r2 est l'ensemble des mots formés par un mot de r1 suivi par un mot de r2, la concaténation. Le langage dénoté par r1+ r2 est l'ensemble des mots de r1 et des mots de r2, l'union. Le langage dénoté par (r1)* est l'ensemble des mots formés par un mot de r1 itérés, l'opération étoile.
Un automate A est un graphe orienté, avec des étiquettes a ou b sur les arêtes. Un noeud est l'état initial et un ensemble de noeuds forme les états finaux. Un mot est accepté s'il suit les arêtes depuis l'état initial juqu'à un état final. Le langage de l'automate L(A) est l'ensemble des mots acceptés. Automate déterministe ou non déterministe. Dans ce dernier cas, on peut le déterminiser.
A toute expression régulière correspond un automate et vice-versa. |