109 lines
1.8 KiB
Markdown
109 lines
1.8 KiB
Markdown
# Exercices REGEXP
|
|
|
|
REGEXP. abb britannique de Regular Expression.
|
|
|
|
|
|
## Exo 1
|
|
|
|
L'alphabet de travail est a,b
|
|
|
|
Pour chaque description en français, proposez une expression régulière.
|
|
* tous les mots sur l'alphabet qui sont de longueur 2.
|
|
(a+b).(a+b)
|
|
|
|
On peut faire le calcul.
|
|
(a+b).(a+b) = a.(a+b)+b.(a+b)
|
|
avec
|
|
a.(a+b) = a.a + a.b
|
|
et
|
|
b.(a+b) = b.a + b.b
|
|
|
|
Donc
|
|
(a+b).(a+b) = a.a + a.b + b.a + b.b
|
|
|
|
En général on n'écrit pas les . qui sont implicites :
|
|
(a+b).(a+b)= aa+ab+ba+bb
|
|
|
|
* tous les mots qui sont de longueur 1.
|
|
a+b
|
|
|
|
* N'importe quel mot
|
|
(a+b)*
|
|
= epsilon + (a+b) + (a+b)(a+b) + (a+b)(a+b)(a+b) + ...
|
|
|
|
* attention
|
|
a+b*
|
|
ça signifie le langage qui contient
|
|
a+ epsilon + b + bb + bbb + bbbb etc
|
|
|
|
* tous les mots qui commencent par un a.
|
|
a.(a+b)*
|
|
|
|
* tous les mots qui terminent par un b.
|
|
(a+b)*.b
|
|
|
|
* tous les mots qui commencent par un a et terminent par un b.
|
|
a.(a+b)*.b
|
|
|
|
* les mots qui commencent et terminent par la même lettre.
|
|
(idée c'est soit je commence et termine par a, soit je commence et termine par b).
|
|
|
|
a.(a+b)*.a + b.(a+b)*.b
|
|
|
|
selon l'interprétation du français de la consigne, on peut considérer que le mot
|
|
a
|
|
commence et termine par a.
|
|
donc il devrait être accepté.
|
|
|
|
Avec interprétation, on va écrire directement
|
|
a + b + a.(a+b)*.a + b.(a+b)*.b
|
|
|
|
* les mots qui contiennent deux a consécutifs.
|
|
informellement :
|
|
... aa ...
|
|
en regexp
|
|
(a+b)*.a.a.(a+b)*
|
|
|
|
* les mots qui contiennent consécutivement bab
|
|
|
|
(a+b)*.b.a.b.(a+b)*
|
|
|
|
* les mots de longueur paire
|
|
On peut regrouper les lettres par paquet de 2.
|
|
epsilon + ((a+b).(a+b))*
|
|
|
|
* les mots avec un nombre pair de a
|
|
|
|
cette question sur l'alphabet {a}
|
|
epsilon + (a.a)*
|
|
|
|
maintenant sur l'alphabet {a,b}, je dois autoriser des b un peu partout.
|
|
epsilon + (b*.a.b*.a.b*)*
|
|
|
|
## Exo 2
|
|
|
|
On souhaite fabriquer un automate à partir d'une expression régulière.
|
|
|
|
Exemple de a.(a+b)*
|
|
Suite au tableau.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|