Scribd
Importer
138 vues2 pages

Corrigé td2 Exo1

Le document présente la résolution d'un exercice portant sur la reconnaissance d'identifiants par automate à états finis. Il décrit d'abord l'unité lexicale, donne l'expression régulière correspondante puis construit l'automate associé qu'il complète et minimise.

Transféré par

Benchehida Cherifa
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
138 vues2 pages

Corrigé td2 Exo1

Le document présente la résolution d'un exercice portant sur la reconnaissance d'identifiants par automate à états finis. Il décrit d'abord l'unité lexicale, donne l'expression régulière correspondante puis construit l'automate associé qu'il complète et minimise.

Transféré par

Benchehida Cherifa
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 Mostaganem

2021-2022
Compilation

Corrigé de l’exercice 1 du TD n°2

Exercice 1 :
Soit l'unité lexicale identificateurs décrite comme suit :

Les identificateurs commencent par le symbole "x" suivi par un nombre binaire. Les 0
non significatifs ne sont pas autorisés.

Exemple d'identificateurs autorisés : x10, x0, x111010, x100


Exemple d'identificateurs non autorisés : x01, y, xx, xx1, x001, x23, x

1) Donner l'expression régulière de l'unité lexicale identificateurs

ER= x(0|1(0|1)*)

2) Donner l'automate à états finis qui reconnait les identificateurs


3) Minimiser l'automate avec la méthode vue en cours.

Représentation tabulaire de l’automate

x 0 1
e0 e1 - -
e1 - e3 e2
e2 - e3 e3
e3 - - -

L’automate est sans état inaccessible, déterministe, mais pas complet. Il faut le rendre
complet.

x 0 1
e0 e1 ep ep
e1 ep e3 e2
e2 ep e3 e3
e3 ep ep ep
ep ep ep ep

On peut maintenant appliquer l’algorithme de minimisation

G1={e2, e3}, G2={e0,e1,ep}


G1_1={e2}, G1_2={e3}, G2_1={e0,ep}, G2_2={e1}

G1_1={e2}, G1_2={e3}, G2_1_1={e0}, G2_1_1={ep}, G2_2={e1}

Chaque groupe contient un seul état donc l’automate complet était minimal.

Vous aimerez peut-être aussi