Scribd
Importer
670 vues4 pages

TD 2

Ce document contient plusieurs exercices sur les automates à états finis. Les exercices portent sur la construction d'automates reconnaissant des langages réguliers définis par des expressions régulières, la déterminisation et la minimisation d'automates, ainsi que des opérations sur les langages.

Transféré par

moslem.haddadi
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
670 vues4 pages

TD 2

Ce document contient plusieurs exercices sur les automates à états finis. Les exercices portent sur la construction d'automates reconnaissant des langages réguliers définis par des expressions régulières, la déterminisation et la minimisation d'automates, ainsi que des opérations sur les langages.

Transféré par

moslem.haddadi
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 de Langages et Automates

Automates à Etats Finis TD2


Exercice 1 :
Soit l'alphabet =
Construire les AFD reconnaissant les langages décrits par les expressions régulières suivantes :
1. a*
2. a+
3. a*b*
4. a+b+

Exercice 2 :
Soit l’alphabet =
1. Proposer un automate fini déterministe qui accepte tous les mots de longueur paire.

2. Donner une expression régulière qui dénote le langage de tous les mots de longueur multiple de 3.

3. Proposer un automate fini déterministe qui accepte le langage de tous les mots de longueur multiple de 3.

4. Proposer un automate fini déterministe qui accepte le langage de tous les mots de longueur paire et
multiple de 3.

Exercice 3 :
On considère l’alphabet {a, b, c}, Construire l’automate fini déterministe équivalent pour chacun des AFN suivants :
Théorie de Langages et Automates

2 ε 3 b 4 ε
a
ε ε ε
8 9
1
a ε c ε
5 6 7

Exercice 4 :
Soit A l’automate suivant :

1. Donner une expression régulière définissant le même langage.

2. Rendre l’automate A déterministe. Soit A’ l’AFD obtenu, donner la table de transitions et la représentation
graphique.

3. A’ est-il minimal? Si non, donnez un automate minimal équivalent A".

4. Appelons L (A") le langage défini par A", donnez un AFD reconnaissant le complémentaire de L (A").
Théorie de Langages et Automates
Exercice 5 :

Considérons l’automate A suivant :

1. Calculer l’automate fini déterministe équivalent à A.


2. Proposer l’automate minimal.

Exercice 6 :
Soit L= ab(a|b)* et M = (a|b)*ba deux langages sur {a,b}
1. Donner les deux automates non déterministes qui reconnaissaient L et M 2.
En déduire les automates de L|M, L.M, L*, M*, (L|M)*

Exercice 7 :
Considérons l’ensemble des mots W = {aab, abba,abb} construit sur l’alphabet Σ={a,b}.
1. Construire l’automate A permettant d’accepter tous les mots possédant au moins une sous chaîne
appartenant à W.
2. Déterminiser l’automate A.
3. Construire l’Automate minimal.

Exercice 8 :
On considère l’automate fini non déterministe suivant :

1. Donner l’automate fini déterministe équivalent.


2. Donner l’automate minimal.
Théorie de Langages et Automates

Exercice 9 :

Exécuter l’algorithme de minimisation pour les automates suivants :

Vous aimerez peut-être aussi