Langages réguliers et automates finis

Un alphabet $\Sigma$ est un ensemble fini de lettres. Un mot est une suite finie de lettres ; le mot vide se note $\epsilon$. L'ensemble de tous les mots est ${\Sigma }^{\ast }$, et un langage est une partie de ${\Sigma }^{\ast }$.

Le vocabulaire préfixe / suffixe / facteur / sous-mot est celui du chapitre chap:textes.

Pour deux langages $L$ et $M$ :

• union : $L\cup M$ ;
• concaténation : $LM=\{uv:u\in L,v\in M\}$ ;
• étoile de Kleene : $L^{\ast }=\{\epsilon \}\cup L\cup LL\cup LLL\cup \cdots$, les concaténations d'un nombre quelconque, éventuellement nul, de mots de $L$.

L'ensemble des langages réguliers sur $\Sigma$ est le plus petit ensemble tel que :

$$\frac{}{\varnothing }\frac{}{\{\epsilon \}}\frac{a\in \Sigma }{\{a\}}\frac{L,M}{L\cup M}\frac{L,M}{LM}\frac{L}{L^{\ast }}$$

C'est encore un ensemble inductif au sens du chapitre chap:induction : les preuves sur les langages réguliers se font par induction sur cette construction.

Une expression régulière est une écriture qui dénote un langage régulier. Le programme fixe les notations : $\varnothing$ pour le langage vide, $\epsilon$ pour le langage réduit au mot vide, $|$ pour l'union, la juxtaposition pour la concaténation, l'étoile pour Kleene.