Scribd
Importer
3 vues2 pages

Théorie des automates et langages formels

Le document présente un examen sur la théorie des langages et automates, comprenant plusieurs exercices sur les automates finis, la déterminisation, la minimisation, et la construction d'expressions régulières. Les exercices incluent des questions sur des langages spécifiques, des constructions d'automates, et des calculs de langages complémentaires. Les étudiants doivent démontrer leur compréhension des concepts d'automates et de langages formels à travers des problèmes pratiques.

Transféré par

dannyyounes7
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
3 vues2 pages

Théorie des automates et langages formels

Le document présente un examen sur la théorie des langages et automates, comprenant plusieurs exercices sur les automates finis, la déterminisation, la minimisation, et la construction d'expressions régulières. Les exercices incluent des questions sur des langages spécifiques, des constructions d'automates, et des calculs de langages complémentaires. Les étudiants doivent démontrer leur compréhension des concepts d'automates et de langages formels à travers des problèmes pratiques.

Transféré par

dannyyounes7
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

Théorie des langages et automates

9 novembre 2022

Durée : 3 heures
Aucun document n’est autorisé

Exercice I.
On se donne l’automate fini suivant :
a, b

a b a
0 1 2 3

1. Parmi les mots suivants, lesquels sont reconnus par l’automate ? aaa, aba, aabbaba, abaaba, aababaaaa,
abcb
2. Déterminiser l’automate.
3. Minimiser l’automate déterministe de la question précédente.
4. Donner une expression régulière qui décrit le langage L1 reconnu par cet automate.

5. On considère maintenant le langage L2 décrit par l’expression régulière : aba(a + b)∗ .


Parmi les mots suivants, lesquels appartiennent au langage ? aaa, aba, aabbaba, abaaba, aababaaaa,
abcb
6. Construire un automate fini déterministe, complet, minimal reconnaissant L2 .

Exercice II.
Avec l’algorithme des automates généralisés vu en cours, calculer une expression rationnelle décrivant le
langage reconnu par
p

b
a
b
b
a
a q
r

Exercice III.
1. Sur l’alphabet {a, b}, on considère le langage L décrit par ab∗ (ε + a(a + b)∗ ). Calculer l’automate
minimal du langage complémentaire de L.
2. Le miroir d’un mot ω = ω1 ω2 . . . ωn est le mot ω 0 = ωn ωn–1 . . . ω1 . On considère le langage L0 contenant
tous les mots miroirs des mots de L. Calculer un automate fini déterministe reconnaissant L0 .

1
Exercice IV
On considère le langage L1 décrit par l’expression régulière e1 = (0 + 01)? 0? et L2 le langage décrit par
e2 = 0? (010? )? sur l’alphabet {0, 1}.
1. Utiliser l’algorithme de Thompson pour construire un automate fini non-déterministe N1 avec transi-
tions spontanées pour L1 = L(e1 ) (donner le graphe de l’automate).
Ne pas simplifier l’expression a priori car vous n’obtiendriez pas l’automate de Thompson demandé.
2. Utiliser la construction vue en cours pour faire disparaître les transitions spontanées. En déduire
l’automate N10 équivalent à N1 , après élimination des ε-transitions.
3. Donner D1 l’AFD obtenu par déterminisation de N10 , avec l’algorithme vu en cours.
4. Donner M1 l’automate obtenu par minimisation de D1 , avec l’algorithme vu en cours.
5. Soit le langage L2 décrit par l’expression régulière e2 = 0? (010? )? .
(a) Donner tous les résiduels de L2
(b) Donner l’automate des résiduels M2 de L2 .
6. À partir de M1 et M2 , construire un automate M3 reconnaissant le langage L1 \L2 .
7. Que peut-on dire de L1 et L2 si le langage reconnu par M3 est vide ?
8. Les expressions rationnelles e1 et e2 décrivent-elles le même langage ? Justifier la réponse.

Page 2

Vous aimerez peut-être aussi