Scribd
Importer
43 vues2 pages

TD 10

Ce document présente des exercices de minimisation d'automates et de calcul de résiduels dans le cadre d'un cours à l'Université Paris 7. Il inclut des exercices sur l'application de l'algorithme de Moore, la conversion d'expressions rationnelles en automates minimaux, et la vérification de l'équivalence entre expressions rationnelles. Les exercices sont accompagnés de diagrammes d'automates et de méthodes algorithmiques pour résoudre les problèmes posés.

Transféré par

soumaila diaby
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
43 vues2 pages

TD 10

Ce document présente des exercices de minimisation d'automates et de calcul de résiduels dans le cadre d'un cours à l'Université Paris 7. Il inclut des exercices sur l'application de l'algorithme de Moore, la conversion d'expressions rationnelles en automates minimaux, et la vérification de l'équivalence entre expressions rationnelles. Les exercices sont accompagnés de diagrammes d'automates et de méthodes algorithmiques pour résoudre les problèmes posés.

Transféré par

soumaila diaby
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é Paris 7 Année 2005–2006 AF3

Feuille de TD no 10 : Minimisation

Exercice 1 : Minimisation
Appliquer l’algorithme de Moore pour calculer l’automate minimal associé aux automates
suivants :

a a
1 2
0 1
a a
a
0 a b 5
b b b b
a
b a
3 4 a, b
b 3 2
a
b
Fig. 1 – Automate A1
Fig. 2 – Automate A2

b a b
1 2 3 4
a

Fig. 3 – Automate A3

Exercice 2 : De l’expression rationnelle à l’automate minimal


Soit l’expression rationelle E = (a + (b + ǫ)b)∗
– Construire l’algorithme de Thompson associé à E.
– Supprimer les ǫ-transitions de l’automate de Thompson.
– Déterminiser l’automate aisni obtenu.
– Compléter puis minimiser l’automate déterminisé.

Exercice 3 : Calcul de Résiduels


Calculer les Résiduels de L1 et L2 par rapport à a (resp. b) :
1. L1 = b(ab)∗ + (ba)∗ b,
2. L2 = a(b + ab)∗ + b∗ (a + bb).

Exercices Maison

Exercice 4 :
On considère le langage L = {w ∈ {a, b}∗ | w contient le facteur bbb}. On souhaite construire
l’automate minimal reconnaissant le langage L. Réaliser ce travail en appliquant les deux méthodes
proposées ci-dessous.
Université Paris 7 Année 2005–2006 AF3

1. Construire un automate non-déterministe reconnaissant L, déterminisez-le, complétez-le et


vérifez que tous les états sont accessibles. Appliquez l’algorithme de Moore pour le minimiser.
2. Écrivez l’expression rationnelle représentant le langage L et construisez l’automate minimal
du langage par calcul des résiduels successifs.
Comparez les deux automates ainsi obtenus.

Exercice 5 :
Proposez une méthode algorithmique pour montrer que deux expressions rationnelles sont
équivalentes. Appliquer cette méthode pour vérifier que b(a + b)∗ a et (b+ a+ )+ désignent le même
langage.

Vous aimerez peut-être aussi