View
2
Download
0
Category
Preview:
Citation preview
La correction des exercices
Exercice 1 :
1) L= {anbm , n>=0, m>0}
Le plus petit mot appartient à L est b L’expression R est : *R a b
Où *
,
| | | ... | ... |n fois
a a aa aa a a
2)
Toutes les chaines qui se terminent par 00 :
*0 |1 00R ;Où *
0 |1 est une combinaison des 0 et/ou des 1 et peut être vide
Toutes les chaînes dont le 10ème symbole, compté à partir de la fin de la chaîne, est un 1.
*0 |1 1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1R
l’expression régulière pour le langage contenant tous les mots begin écrits avec des majuscules et minuscules mélangés : bEgin, BEGin, begiN, BEGIN, … R≡ (B│b)(E│e)(G│g)(I│ i)(N│n)
Exercice 02 :
L’ automate AEF qui permet de le reconnaitre le langage L= {anbm , n>=0, m>0}
1)
2) L’ automate AEF qui permet de le reconnaitre l’expression régulière *0 |1 00R
3) L’automate AEF qui permet de le reconnaitre l’expression régulière
*0 |1 1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1 0 |1R
4) L’ automate AEF qui permet de le reconnaitre l’expression
R≡ (B│b)(E│e)(G│g)(I│ i)(N│n)
Exercice 03 :
Pour trouver A sans transition on a besoin de la représentation graphique
On applique l’algorithme :
Donc :
Et F
Pour la transition (2)
Pour la transition (3)
Finalement on obtient :
Exercice 04:
On A non déterministe il faut la rendre déterministe, on doit appliquer l’algorithme comme suit :
On commence à développer les états à partir de l’état initial
A Q
A b
0 1,2 - 1,2 1,2,3 0,2,3
1,2,3 0,1,2,3 0,2,3 0,2,3 0,1,2 -
0,1,2,3 0,1,2,3 0,2,3 0,1,2 1,2,3 0,2,3
Donc on a les états (1,2,3),(0,2,3),(0,1,2,3) F
Il suffit de renommer les états :
A Q
A b
q0={0} q1 - q1={1,2} q2 q3
q2={1,2,3} q4 q3 q3={0,2,3} q5 -
q4={0,1,2,3} q4 q3 q5={0,1,2} q2 q3
Exercice 05 :
- On doit trouver une définition régulière permettant de reconnaître les numéros d’immatriculation composés de :
3 à 5 chiffres ne commençant par le chiffre 0 : 1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9ChSZero (chiffre sans 0)
| 0Chiffre ChSZero
| |Chiffres ChSZeroChiffreChiffre Chiffre ChiffreChiffre
| | | ... | | |LetSW A B C V X Y (Lettre sans W)
| | | ... | | | |Lettre A B C V W X Y (W est inclus)
| |immat Chiffres LettreLetSW LetSWLettre ChiffreChSZero ChSZeroChiffre
Analyse lexicale : Lex
Exercice 01 :
Expliquez la signification des symboles suivants dans le contexte d’expression régulière Lex :
*,+,|, ?,[ ],{},(),\, ‘’, . ,^,$,/ (voir le tableau dessus)
Exercice 02 :
1) Le motif ?ab peut filtrer les mots:
2) Le Motif peut filtrer les mots :
Exercice 03 :
NbrDec(les nombres décimaux) Lex : ? 0 9 \. 0 9 ?
Ident (les identifiants de variables)Lex:
OR (les opérateurs relationnels >, <, …) Lex: " " | " " | " " | " " | " "
NbrFlot (les nombres flottants) Lex: ? 0 9 \. 0 9 ? ? 0 9 ?Ee
On peut utiliser la définition régulière :
Chiffre 0 9
Frac \.{Chiffre}
Exp [Ee][+-] ?{Chiffre}
NbrFlot [+-] ?{Chiffre}{Frac} ?{Exp} ?
Recommended