Scribd
Importer
11 vues1 page

Exercices sur les langages et automates

Le document présente des exercices sur la théorie des langages et des automates, incluant des expressions régulières et des automates finis. Il aborde des concepts tels que les relations d'inclusion des langages, la simplification d'expressions régulières et la construction d'automates pour divers langages. Les exercices sont destinés aux étudiants de niveau L2CS à l'Institut Supérieur d'Informatique de Tunis.

Transféré par

Chaima Mestiri
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
11 vues1 page

Exercices sur les langages et automates

Le document présente des exercices sur la théorie des langages et des automates, incluant des expressions régulières et des automates finis. Il aborde des concepts tels que les relations d'inclusion des langages, la simplification d'expressions régulières et la construction d'automates pour divers langages. Les exercices sont destinés aux étudiants de niveau L2CS à l'Institut Supérieur d'Informatique de Tunis.

Transféré par

Chaima Mestiri
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é de Tunis El Manar Matière : Théorie des langages et

Institut Supérieur d’Informatique (ISI) automates.


Département Génie Logiciel
et Systèmes d’Information (GLSI) 12. Le langage contenant les mots comportant un nombre pair de ‘a’ et un nombre impair
Niveau : L2CS
de ‘b’.
13. Le langage contenant les mots où le nombre d’occurrence de ‘b’ est divisible par 3.
14. Le langage contenant les mots qui commencent par ‘aa’ et se termine par ‘bb’.
TD N°2

Exercice 1: Exercice 5:
Déterminer les relations d’inclusion des langages décrits par les expressions régulières Soient Σ = {a,b,c,d} ; F= {q4 , q5}
suivantes :
1. (a|b)* δ q0 q1 q2 q3 q4 q5
2. a*|b q0 A b c - d -
3. a*|b* q1 - a d c b -
q2 - d c - d b
Exercice 2:
Simplifier les expressions régulières suivantes : q3 - b a - d c
1. a|a*|ε q4 A - - b c d
2. (a a)∗| a(aa)∗ q5 A - - b c d
3. ((aba)*)*
4. ab*|b*
5. (a|a∗| b∗| a| b) L = {aaabcd; abababdcab; dcddcca; adcccbbabba; adccccba}
6. (ε|a*|b*|a|b|aa|bbb)
7. a | (a|b)*b | (ab)* | (ba)* 1. Vérifier si le langage L est reconnu par A.
2. Donner L' tel que L' ⊂ L et L ' = { w : w reconnu par A}
Exercice 3 :
Soit l'alphabet Σ = {a,b}. Exercice 6 :
Construire les automates finis reconnaissants les langages décrits par les expressions Soit X={a,b} et soient :
régulières suivantes L1={w ϵ X* / w=(ab)*(aa|a)}
1. a* L2={w ϵ X* / w=ab*a|ab*cb*|ab*cb*a}
2. a+
3. a*b* 1. Construire les automates A1 et A2 correspondant aux langages L1 et L2 respectivement.
4. a+b+ 2. Construire un automate pour L(A1) ∪ L(A2), L(A1) ∩ L(A2),L(A1) . L(A2), L(A1)* et
5. aab* (L(A1))c.
6. a*bbb
7. bab|a|b Exercice 7 :
On considère l'alphabet Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. On voudrait construire l'automate
acceptant les entiers naturels représentés en système décimal, qui son multiple de 3 (la chaîne
Exercice 4 : vide ne sera pas acceptée).
Donner les ER et les AFN sur {a,b} reconnaissant : 1. Construire l’automate des entiers naturels (en base 10) qui sont multiples de 3 et qui
1. Le langage vide. commencent par 1 (exemple 12, 15, etc.)
2. Le langage contenant le mot {ε}. 2. Expliquer comment généraliser votre approche pour un automate qui accepte tous les
3. Le langage contenant le mot {a}. entiers naturels multiples de 3.
4. Le langage contenant tous les mots sur {a,b}.
5. Le langage contenant les mots ayant au plus une occurrence de ‘a’. INDICATION : Un nombre décimal est multiple de 3 si et seulement si la somme de ses
6. Le langage contenant les mots ayant au moins une occurrence de ‘a’. chiffres est un multiple de 3.
7. Le langage contenant les mots ayant pour préfixe ‘aba’.
8. Le langage contenant les mots ayant pour suffixe ‘aba’.
9. Le langage contenant les mots ayant pour facteur ‘aba’.
10. Le langage contenant les mots de longueur paire.
11. Le langage contenant les mots de longueur impaire

Vous aimerez peut-être aussi