Un langage sera appelé
rationnel s'il découle d'un langage simple (rien, un mot, un ensemble fini de mot etc) et d'opérations sur les langages (union, concaténation, étoile de Kleene). Ce sont de ces langages dont nous allons chercher les REGEX.
Définition
Soit \( \Sigma\) un alphabet. On note \( LR(\Sigma)\) l'ensemble des langages rationnels construit de la manière suivante.
\begin{eqnarray*}
& &\varnothing\in LR(\Sigma)\\
& &\{\varepsilon\}\in LR(\Sigma)\\
\forall x\in \Sigma & & \{x\}\in LR(\Sigma)\\
\forall L_1, L_2\in LR(\Sigma) & & L_1\cup L_2 \in LR(\Sigma)\\
\forall L_1, L_2\in LR(\Sigma) & & L_1L_2 \in LR(\Sigma)\\
\forall L\in LR(\Sigma) & & L^* \in LR(\Sigma)
\end{eqnarray*}
Remarque
Une autre manière de lire cette définition est :
- L'ensemble vide est un langage rationnel
- Le mot vide est un langage rationnel
- Toutes les lettres sont des langages rationnels
- L'union de langage rationnel est un langage rationnel
- La concaténation de langage rationnel est un langage rationnel
- L'étoile de Kleene de langage rationnel est un langage rationnel.
Remarque
ATTENTION : \( LR(\Sigma)\) est l'ensemble des langages rationnels. C'est donc un ensemble d'ensemble.
Exercice
Décrire \( LR(\varnothing)\) , \( LR(\{\varnothing\})\) et \( LR(\{a\})\) .
Proposition
Soient \( \Sigma\) un alphabet et \( m\in \Sigma^{*}\) un mot alors \( \{m\}\in LR(\Sigma)\)
L'Exercice suivant permet de réaliser la démonstration.
Exercice
Démontrer la proposition précédente par récurrence sur la taille du mot \( m\) .
Proposition
Soient \( \Sigma\) un alphabet et \( L\subseteq \Sigma^*\) un langage de cardinalité fini alors \( L\in LR(\Sigma)\)
L'Exercice suivant permet de réaliser la démonstration.
Exercice
Démontrer la proposition précédente par récurrence sur la cardinalité de \( L\) .
Exercice
La réciproque de cette proposition est-elle vraie ?