Scribd
Importer
78 vues3 pages

Théorie des Langages : Exercices

Le document présente plusieurs exercices sur les automates à états finis (AEF) dont la construction d'AEF pour différents langages réguliers, la vérification de l'appartenance de mots à des langages, la déterminisation et la minimisation d'AEF ainsi que la détermination de langages associés à des AEF.

Transféré par

Møh Męd
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
78 vues3 pages

Théorie des Langages : Exercices

Le document présente plusieurs exercices sur les automates à états finis (AEF) dont la construction d'AEF pour différents langages réguliers, la vérification de l'appartenance de mots à des langages, la déterminisation et la minimisation d'AEF ainsi que la détermination de langages associés à des AEF.

Transféré par

Møh Męd
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

Université Abou Bekr Belkaid – Tlemcen Année universitaire 2023-2024

Faculté des sciences 2eme année Licence Informatique « S4 »


Département Informatique Théorie des Langages

TD N° 3
Les Automates AEF
Exercice 1 :
Proposer un AEF pour chacun des langages suivants :
1- L1 ={(a/b)*}
2- L2 ={(a/b)+}
3- L3 = {(ab)*}
4- L4 ={(ab)+}
5- L5 ={a*b+}
6- L6 ={a*b*}
7- L={a*(b/c)d+}
8- L={(b/c)nd / n>=2 }
9- L={an / n est pair}
10- L={an / n est impair}
11- L={an bm / n est pair , m est impair}

Exercice 2
Soit l’AEF suivant :

1. Montrer si les mots suivants appartiennent à L(A) : bba, ba, bb .


2. Rendre l’AEF A déterministe.
Université Abou Bekr Belkaid – Tlemcen Année universitaire 2023-2024
Faculté des sciences 2eme année Licence Informatique « S4 »
Département Informatique Théorie des Langages

Exercice 3
Rendre les AEFs suivants déterministes :
A1 : A2

A3 A4

Exercice 4 :
Soit l’AEF A=({a,b}, {q0,……, q5}, q0, , {q0, q4}), avec  définie par :
Université Abou Bekr Belkaid – Tlemcen Année universitaire 2023-2024
Faculté des sciences 2eme année Licence Informatique « S4 »
Département Informatique Théorie des Langages

1. Montrez que bba  L(A)


2. Minimiser l’AEF A
3. Déterminer L(A)

Exercice 5
Soit l’AEF A= ({0,1}, {s0,……, s5}, s0, , {s0, s4}), avec  définie par :

Construire l’AEF A minimal et équivalent à A


En déduire L(A)

Exercice 6

Vous aimerez peut-être aussi