Scribd
Importer
26 vues2 pages

td2 Compilation

Ce document contient plusieurs exercices sur les expressions régulières et les automates à états finis. Les exercices portent sur la définition d'expressions régulières correspondant à des langages donnés et la construction d'automates équivalents.

Transféré par

djaafarnedjla7
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
26 vues2 pages

td2 Compilation

Ce document contient plusieurs exercices sur les expressions régulières et les automates à états finis. Les exercices portent sur la définition d'expressions régulières correspondant à des langages donnés et la construction d'automates équivalents.

Transféré par

djaafarnedjla7
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TD N°2

Exercice 01 :
1. Soit l’alphabet A={a, b}. Définir l’expression régulière R correspondant au langage régulier
L= { 𝑎 𝑏 où n>=0, m>0}
2. Soit l’alphabet A = {0,1}. Définir les expressions régulières correspondant aux langages ci-
dessous :
- Toutes les chaînes qui se terminent par 00.
- Toutes les chaînes dont le 10ème symbole, compté à partir de la fin de la chaîne, est un 1.
3. Définir 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, …

Exercice 02 :
Pour chaque langage de l’exercice 1, donner un automate AEF qui permet de le reconnaitre.

Exercice 03 :
Soit l’automate AEF A avec les ε-transitions
États Symbole d’entrée
a B ε
Init 0 1, 2
1 3 1
2 2 4
3 3 5
4 4 5
Final 5
- Trouver l’automate AEF B sans ε -transitions équivalent à l’automate A.

Exercice 04 :
Soit l’automate AEF A :

- L’état initial est 0, et l’unique état final est 3.


a) Construire un automate à états finis déterministe à partir de la table de transition (équivalent
à A).

Exercice 05 :
- Donner 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,
suivis de 2 lettres majuscules en excluant WW,
terminant par 2 chiffres en excluant 00
Exemples de numéros acceptés :123WA01 64725AA45

1
Exercice 03
Donner les définitions régulières en Lex permettant de définir les unités lexicales suivantes :
 NbrDec (les nombres décimaux) ;
 Ident (les identifiants de variables) ;
 OR (les opérateurs relationnels >, <, …);
 NbrFlot (les nombres flottants).

Vous aimerez peut-être aussi