Scribd
Importer
97 vues3 pages

Automates Finis : Exercices Avancés

Ce document contient plusieurs exercices sur les automates finis et l'analyse lexicale. Les exercices portent sur la reconnaissance de mots par des automates, la construction d'automates déterministes équivalents à des automates non déterministes, et la minimisation d'automates.

Transféré par

mahditrigui146
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
97 vues3 pages

Automates Finis : Exercices Avancés

Ce document contient plusieurs exercices sur les automates finis et l'analyse lexicale. Les exercices portent sur la reconnaissance de mots par des automates, la construction d'automates déterministes équivalents à des automates non déterministes, et la minimisation d'automates.

Transféré par

mahditrigui146
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

SÉRIE DE TD

(Analyse Lexicale : Automates Finis)

EXERCICE N°1 :
On considère deux automates A1 et A2 sur l’alphabet {a,b}.

a) Dans quel état se trouve l’automate A1 après lecture des mots a, ab, abb, abba ? Après
lecture du mot e ?
b) Lesquels de ces mots sont reconnus par l’automate A1 ?
c) Que se passe-t-il quand on donne le mot aab à lire à l’automate A1 ?
d) Les mots aba2b, a2ba2b, ab4 et b3a2 sont-ils reconnus par l’automate A1 ?
e) Décrire les mots reconnus par l’automate A1.
f) Après lecture du mot b3a2, dans quel état se trouve l’automate A2 ?
g) S’il n’a lu aucun a, dans quel état se trouve l’automate A2 ?
h) Dans quels cas l’automate A2 se trouve-t-il dans l’état 1 ?
i) Dans quels cas arrive-t-il à l’état final 2 ? Quels mots reconnaît-il ?

EXERCICE N°2

Soit l’alphabet A ={a}


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.
2/2

EXERCICE N°3

On considère l’alphabet {a, b, c}, Construire l’automate fini déterministe équivalent pour chacun des
AFN suivants :

EXERCICE N°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").

EXERCICE N°5

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

Vous aimerez peut-être aussi