Théorie des langages : Cours les expressions régulières
Télécharger PDFLes Expressions Régulières
M. Adil KENZI 1
Plan-Expressions Réguliéres
Introduction
Expressions Régulières
Définition
Exemples
Transformation des expressions régulières en des automates
Transformation des automates en des expressions régulières
Lemme de l’étoile
Conclusion2 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ères opérationnelle: par une sorte de machine (l’automate).
Par exemple:
Il est inconcevable que pour faire un grepsur Unix ou Linux on doit définir un automate.
De même pour utiliser des logiciels d’analyse lexicale comme Lexou Flex
on doit spécifier les lexiques. On préfère faire ceci de manière concise et simple.
Les expressions régulières permettent de le faire de manière déclarative.3 Expressions régulières Soit ∑ un alphabet. Définition Les expressions régulières sur ∑ sont définies inductivement:
εet ∅sont des expressions régulières sur ∑ Si a∈∑ alors aest une expression régulière sur ∑
Si eete′sont des expressions régulières sur ∑ alors e + e′est une expression régulière.
Si eete′sont des expressions régulières sur ∑ alors e·e′est une expression régulière.
Si eest une expression régulière sur ∑ alors e*est une expression régulière sur ∑.
L’ensemble des expressions régulières est dénoté par ER(∑).4 Expressions Régulières
Définition La sémantique des expressions régulières est donnée par l’application L : ER(∑) →P(∑*) qui associe à eun langage L(e). L’application L est définie inductivement:
L(ε) = {ε}, L(∅) = ∅et L(a) = {a}.
L(e + e′) = L(e) ∪L(e′).
L(e·e′) = L(e) · L(e′).
L(e*) = L(e)*.
On dit qu’un langage L est régulier si et seulement si il existe une expression régulière e telle que L(e) = L.5 Convention et notations
Nous voulons aussi pouvoir écrire des expressions comme a + b + c à la place de (a + b) + c et a + b∗ à la place de (a + (b∗ )). Pour éviter les ambigüités nous permettons l’utilisation des parenthèses et admettons les priorités suivantes dans un ordre décroissant:1.* 2..3.+ 6
Convention et notation
Nous écrivons aussi LL′à la place de L · L′.
Donc les expression e1 + e2 * et e1+(e2)* dénote les mêmes ensembles. Ainsique e1 +e2 .e
3 ete1 +(e2 .e3 ).
Exemple
Le langage constitué des mots sur {a, b} avec nombre pair de a ou nombre impair de b peut être décrit par l’expression régulière:((ab ∗
a+ b)∗ + (ba∗ b+ a)∗ ba∗ .7 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 chaines de 0 et de 1 qui ne contiennent pas deux 1 consécutifs.8 Expressions régulières
lois algébriques
Soient R, S et T trois expressions régulières
L’associativité :
R+(S+T)= (R+S)+T et R(ST)= (RS)T
La commutativité:
R +S= S+R
RS≠ SR
La distributivité :
R(S+T) = RS+RT et (S+T)R=SR+TR
L’identité :
R+Ø=Ø+R=R et Rε=εR=R
Annihilateur :
RØ = ØR=Ø
Idempotent :R+R=R R
+ =RR*=R*R
R*=(R*)*= R*R*=ε+R*9 Les expressions régulières
lois algébriques
Autres lois algébriques importantes sur les expressions régulières
Soient R, S et T trois expressions régulières
Ф*= ε* = ε.
R* = R*R* = (R*)* = R + R*.
R* = ε+ R* = ε+ RR* = (ε+ R)* = (ε+ R)R*.
R* = (R + R2 + ...+ Rk )* = ε+ R + R2 + ...+ Rk-1 + Rk R* pour tout k ≥1.
R*R = RR*.
(R + S)* = (R* + S*)* = (R*S*)* = (R*S)*R* = R*(SR*)*.
R(SR)* = (RS)*R.
(R*S)* = ε+ (R + S)*S and (RS*)* = ε+ R(R + S)*.10 Exemples-Application des lois algébriques
Exemple 1 : En se basant sur les lois algébriques, on peut démontrer les égalités suivantes
(a + aa)(a + b)* = a(a + b)*
Démonstration : (a + aa)(a + b)* = (a + aa)a*(ba*)* (R + S)* = R*(SR*)* = a(ε + a)a*(ba*)* R = Rεet la distributivité de • = aa*(ba*)* (ε + R)R* = R* = a(a + b)* (R + S)* = R*(SR*)*. 1112 Exemple2
Montrer que a*(b + ab*) = b + aa*b*. Démonstration : a*(b + ab*) = ( ε+ aa*)(b + ab*) R* = ε+ RR* = b + ab* + aa*b + aa*ab* la distributivité de • = b + (ab* + aa*ab*) + aa*b+ est commutatif et
associatif = b + (ε + aa*)ab* + aa*b R = Rεet la distributivité •
= b + a*ab* + aa*bR* = ε+ RR* = b + aa*b* + aa*bR*R = RR* = b + aa*(b* + b) la distributivité de •
= b + aa*b*. R* = R* + R Théorème de Kleene
Théorème Soit ∑ un alphabet et L ⊆∑∗.
L est régulier si et seulement si L est reconnu par un automate d’états finis.
Plus encore,
Soient L, L1 et L2 deux langages réguliers 1.L
1 UL
2 est régulier2.L 1 L2 est régulier3.L * est régulier
4.le Complément de L est régulier5.L 1
. L
2 est régulier13 Equivalence Expressions Régulières/Automates
Définition d’un automate avec epsilon transitionà partir d’une expression régulière Définition de l’expression régulière définissant le langage accepté par un automate fini déterministe14 Du ER à un ε-NFA: Base
Symbolea:ε: ∅:15 aε État initial
État final
ER à ε-NFA: –UnionE 1E 2
Automate avec epsilon transitions associé à l’expression régulière E1 +E2 εεε ε
Soient E1, E2 deux expressions régulières. L’automate avec epsilon transitions ci-dessous reconnait le langage défini par l’expression régulière E1+E216 État initial
État final
ER à ε-NFA: ConcatenationE 1E 2
Automate avec epsilon transitions associé à l’expression régulière E1 E2 ε
SoientE1,E2deuxexpressionsrégulières.
L’automateavecepsilontransitionci-dessous
reconnaitlelangagedéfiniparlaconcaténationdeE1.E2 17
ER à ε-NFA: la fermeturede kleeneE E*ε εεε Soit Eune expressions régulière. L’automate avec epsilon transition ci-dessous reconnait le langage défini par E*18 Exercice
(1) Construction du ε-NFA associé à l’expression régulière suivante : R= (a+b)*(aa+bb)(a+b)* (2) Déduire l’automate déterministe associé19 Transformation d’un DFA en une Expression Régulière
Méthode d’élimination d’état Soit M un automate. On cherche une expression régulière dénotant le langage reconnu par M. On procède par suppression successive de transitions et d’états, en remplaçant d’autres étiquettes par des expressions étiquettes.
1.AjouteràMdeuxnouveauxétats,notésαetw,etles
transitions(α,ε,q0 )pourq0 l’étatinitial;et(qn ,ε,w)pourqn ∈F. 2.Itérer les réductions suivantes tant que possible :
s’il existe deux transitions (q
i ,x,qj ) et (q
i ,y,qj ), les remplacer par la transition (qi ,x +y, qj )
supprimer un état q (autre que a et w) et remplacer, pour tous les états différents p, r q, les transitions (p,x,q), (q,y,q), (q,z, r ), par la transition (p, xy* z, r ).20 Elimination d’états21 Elimination de l’état S et remplacement des transitions Exemple (1) Déterminer l’expression régulière associée au langage reconnu par l’automate en appliquant l’algorithme de l’élimination des états 22
Algorithme-premiéreétape
Algorithme-Elimination de l’état 1
Algorithme-Elimination de l’etat0
Algorithme-Remplacement des transitions Algorithme-Elimination de l’état 2
Algorithme-Elimination de l’état 2
l’expression régulière associée à l’automate est : R = b∗ aa∗ b(aa∗ b+bb∗ aa∗ b)∗ = (a+b)∗ ab (par application des différentes lois algébriques)
Simplification de l’expression régulière obtenue
Lemme de l’étoile (pumpinglemma)
Siun langage Lsur un alphabet (L *) estrégulier, alors n IN*(qui dépend de L) tel u Lavec |u|
n,et il existe une décomposition de uen trois parties u = fghtelle que :
1.g
2.|fg| n
3.k0, fgk hL30 Prouver qu’un Langage est irrégulier
Soit l’alphabet = {a, b} Le langage L = a+ est régulier (on peut construire facilement le DFA le reconnaissant) alors
u L, |u| 1
u = fgh, f=a*, g=a, h=a*, g k 0, fgk h= a*(a)k a* L
Le langage L = a*b* est régulier (construction du DFA le reconnaissant) alors
u L, |u| 1
u = fgh, f=a*, g=ai , h=a*b*, g k 0, fgk h= a*(ai )k a*b* L
Le langage L = am bm , m IN n’est pas régulier, car
u L, |u| 2
u = fgh, f=am-i , g=ai , h=bm , g k 0, fgk h= am-i (ai )k bm L
u = fgh, f=am-i , g=ai bi , h=bm-j , g k 0, fgk h= am-i (ai bj )k bm-j L
u = fgh, f=am , g=bj , h=bm-j , g k 0, fgk h= am (bj )k bm-j L31 Conclusion
Automates Fini Déterministes
Automates Fini non déterministes
Automates avec epsilon transition
Expressions Régulières
32