| Alphabet, mot, préfixe, suffixe, facteur, sous-mot. |
Le mot vide est noté 𝜀. |
| Langage comme ensemble de mots sur un alphabet. Opérations régulières sur les langages (union, concaténation, étoile de Kleene). Définition inductive des langages réguliers. |
|
| Expression régulière. Dénotation d’un langage régulier. |
On introduit les expressions régulières comme un formalisme dénotationnel pour les motifs. On note l’expression dénotant le langage vide ∅, celle dénotant le langage réduit au mot vide 𝜀, l’union par |, la concaténation par juxtaposition et l’étoile de Kleene par une étoile. |
| Expressions régulières étendues. |
Le lien est fait avec les expressions régulières de la norme POSIX, mais on ne développe aucune théorie supplémentaire à leur sujet et aucune connaissance au sujet de cette norme n’est exigible. |