Théorie des langages : Cours les expressions régulières
Télécharger PDFLes Expressions Régulières
M. Adil KENZI
Plan
Introduction
Expressions Régulières
Définition
Exemples
Transformation des expressions régulières en automates
Transformation des automates en expressions régulières
Lemme de l’étoile (pumping lemma)
Conclusion
Pourquoi les Expressions Régulières?
Motivation :
On cherche une notation plus concise et plus simple que les automates pour décrire les langages.
Problème : Les automates offrent la possibilité de décrire des langages de manière opérationnelle, par une sorte de machine. Par exemple, il est inconcevable que pour faire une recherche de texte sur Unix ou Linux, on doive définir un automate.
De même, pour utiliser des logiciels d’analyse lexicale comme Lex ou Flex, on doit spécifier les lexèmes. On préfère le faire de manière concise et simple.
Les expressions régulières permettent de décrire ces langages de manière déclarative.
Définition des Expressions Régulières
Soit ∑ un alphabet. Les expressions régulières sur ∑ sont définies inductivement :
- ε (la chaîne vide) et ∅ (l’ensemble vide) sont des expressions régulières sur ∑.
- Si a ∈ ∑, alors a est une expression régulière sur ∑.
- Si e et e′ sont des expressions régulières sur ∑, alors e + e′ (union) est une expression régulière.
- Si e et e′ sont des expressions régulières sur ∑, alors e·e′ (concatenation) est une expression régulière.
- Si e est une expression régulière sur ∑, alors e* (fermeture de Kleene) est une expression régulière.
L’ensemble des expressions régulières est noté par ER(∑).
Sémantique des Expressions Régulières
La sémantique des expressions régulières est donnée par l’application L : ER(∑) → P(∑*), qui associe à chaque expression régulière e un langage L(e). L’application L est définie inductivement :
- L(ε) = {ε}, L(∅) = ∅ et L(a) = {a} pour a ∈ ∑.
- L(e + e′) = L(e) ∪ L(e′).
- L(e·e′) = L(e) · L(e′).
- L(e*) = L(e)*.
Un langage L est régulier si et seulement s’il existe une expression régulière e telle que L(e) = L.
Conventions et Notations
Pour éviter les ambiguïtés, nous utilisons les parenthèses et admettons les priorités suivantes dans un ordre décroissant :
- Fermeture de Kleene (*)
- Concatenation (·)
- Union (+)
Nous écrivons aussi L·L′ à la place de L·L′ et L* à la place de L*.
Par exemple, les expressions e1 + e2* et e1 + (e2)* désignent le même ensemble de chaînes.
Exemples d’Expressions Régulières
- L(01) = {01}.
- L(01 + 0) = {01, 0}.
- L(0(1 + 0)) = {01, 00}.
- L(0*) = {ε, 0, 00, 000, ...}.
- L((0 + 10)*(ε + 1)) = toutes les chaînes de 0 et de 1 qui ne contiennent pas deux 1 consécutifs.
Lois Algébriques des Expressions Régulières
Soient R, S et T trois expressions régulières.
- Associativité : R + (S + T) = (R + S) + T et R·(S·T) = (R·S)·T.
- Commutativité : R + S = S + R. (La concatenation n’est pas commutative : R·S ≠ S·R.)
- Distributivité : R·(S + T) = R·S + R·T et (S + T)·R = S·R + T·R.
- Identité : R + ∅ = ∅ + R = R et R·ε = ε·R = R.
- Annihilateur : R·∅ = ∅·R = ∅.
- Idempotence : R + R = R et R* = R*·R* = R* + R.
- R* = ε + R* = ε + R·R* = (ε + R)* = (ε + R)·R*.
- R*·R = R·R*.
- (R + S)* = (R* + S*)* = (R·S*)* = (R·S)*·R* = R*(S·R*)*.
- R·(S·R)* = (R·S)*·R.
- (R·S)* = ε + (R + S)*·S et (R·S*)* = ε + R·(R + S)*.
Exemples d’Application des Lois Algébriques
Exemple 1
Montrer que (a + aa)·(a + b)* = a·(a + b)*.
Démonstration :
(a + aa)·(a + b)* = (a + aa)·a*·(b·a*)* = a·(ε + a)·a*·(b·a*)* = a·a*·(b·a*)* = a·(a + b)*.
Exemple 2
Montrer que a*·(b + ab*) = b + aa*b*.
Démonstration :
a*·(b + ab*) = (ε + aa*)·(b + ab*) = b + ab* + aa*b + aa*ab* = b + (ab* + aa*b) + aa*b.
En utilisant la distributivité et l’associativité :
ab* + aa*b = a·(b* + a*b) = a·(ε + a)*·b = a*·ab*.
Donc :
b + a*·ab* + aa*b = b + a*·(b* + b) = b + aa*b*.
Théorème de Kleene
Soit ∑ un alphabet et L ⊆ ∑*.
L est régulier si et seulement si L est reconnu par un automate à états finis.
Plus précisément, si L1 et L2 sont deux langages réguliers, alors :
- L1 ∪ L2 est régulier.
- L1 ∩ L2 est régulier.
- L* est régulier.
- Le complément de L est régulier.
- L1 · L2 est régulier.
Transformation d’un Automate en Expression Régulière
Pour transformer un automate en expression régulière, on utilise la méthode d’élimination d’état.
Soit M un automate. On cherche une expression régulière désignant le langage reconnu par M. Voici les étapes :
- Ajouter deux nouveaux états, notés α et w, avec les transitions (α, ε, q0) pour q0 l’état initial et (qn, ε, w) pour qn ∈ F.
- Itérer les réductions suivantes tant que possible :
- Si deux transitions (qi, x, qj) et (qi, y, qj) existent, les remplacer par une seule transition (qi, x + y, qj).
- Supprimer un état q (autre que α et w) et remplacer, pour tous les états p et r différents de q, les transitions (p, x, q), (q, y, q), (q, z, r) par une transition (p, xy*z, r).
Exemple de Transformation d’un Automate en Expression Régulière
Déterminer l’expression régulière associée au langage reconnu par l’automate suivant en appliquant l’algorithme d’élimination des états.
L’expression régulière associée à l’automate est : R = b*aa*b(aa*b + bb*aa*b)* = (a + b)*ab (après simplification à l’aide des lois algébriques).
Lemme de l’Étoile (Pumping Lemma)
Si un langage L sur un alphabet ∑ (L ⊆ ∑*) est régulier, alors il existe un entier n (qui dépend de L) tel que pour toute chaîne u ∈ L avec |u| ≥ n, il existe une décomposition u = xyz telle que :
- y ≠ ε.
- |xy| ≤ n.
- Pour tout k ≥ 0, xykz ∈ L.
Comment Prouver qu’un Langage est Irrégulier?
Soit l’alphabet ∑ = {a, b}.
- Le langage L = a* est régulier (on peut construire facilement un DFA le reconnaissant).
- Le langage L = a*b* est régulier (construction du DFA le reconnaissant).
- Le langage L = {ambm | m ∈ ℕ} n’est pas régulier, car pour toute décomposition u = xyz, il existe un k tel que xykz ∉ L.
Conclusion
Les expressions régulières et les automates à états finis sont des outils complémentaires pour décrire et reconnaître les langages formels. Les automates finis déterministes (DFA), les automates finis non déterministes (NFA) et les automates avec transitions ε permettent de modéliser des langages, tandis que les expressions régulières offrent une notation concise.
FAQ
Qu’est-ce qu’une expression régulière?
Une expression régulière est une notation mathématique utilisée pour décrire des ensembles de chaînes de caractères sur un alphabet donné. Elle permet de définir des langages de manière concise.
Comment les expressions régulières sont-elles liées aux automates?
Le théorème de Kleene établit que tout langage régulier peut être reconnu par un automate à états finis et vice versa. Cela signifie qu’il existe une équivalence entre les expressions régulières et les automates.
À quoi sert le lemme de l’étoile?
Le lemme de l’étoile (ou pumping lemma) est un outil utilisé pour prouver qu’un langage donné n’est pas régulier en montrant qu’il ne satisfait pas les conditions du lemme.