Expressions régulières
Les expressions régulières comme notation de langages : lettres, ε, ∅, union, concaténation, étoile, priorités, langage dénoté, équivalence de deux expressions et théorème de Kleene.
- 21 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Expression régulière : de quoi s'agit-il ?
Voir la réponse
Formule construite avec ∅, ε et des lettres, combinés par l'union (+), la concaténation et l'étoile, qui dénote un langage.
L'expression est un texte, le langage est l'ensemble de mots qu'elle dénote : a(a+b)* est une expression, l'ensemble des mots qui commencent par a est son langage.
Dans l'expression ab*+c, sur quoi porte l'étoile ?
- Sur la lettre b seulement
- Sur ab
- Sur ab+c en entier
- Sur b et sur c
Voir la réponse
Sur la lettre b seulement
L'étoile est l'opération la plus prioritaire : elle ne porte que sur le plus petit morceau à sa gauche, ici b. Le langage est {a, ab, abb, …} ∪ {c}.
L'union de deux expressions se note + en théorie des langages, et … dans les outils comme grep -E ou Python.
Voir la réponse
L'union de deux expressions se note + en théorie des langages, et | dans les outils comme grep -E ou Python.
Le piège : dans ces outils, + n'est plus l'union mais un quantificateur, « une fois ou plus ». a+b y décrit ab, aab, aaab… et non le langage {a, b}, qui s'écrit a|b.
Langage régulier : de quoi s'agit-il ?
Voir la réponse
Langage que dénote une expression régulière, ou, ce qui revient au même, que reconnaît un automate fini.
Tout langage fini est régulier. Mais aⁿbⁿ ne l'est pas : un automate fini ne peut pas compter jusqu'à n quand n n'est pas borné.