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} ?