Scribd
Importer
174 vues4 pages

EPI TD4 Correction

Le document présente deux exercices sur la théorie des langages. Le premier exercice demande de trouver des automates déterministes équivalents à deux automates donnés et de déterminer leur grammaire régulière associée. Le deuxième exercice demande de construire des automates équivalents et complémentaires à partir de deux automates donnés.

Transféré par

Doucson Seydou Fily Mallé
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
174 vues4 pages

EPI TD4 Correction

Le document présente deux exercices sur la théorie des langages. Le premier exercice demande de trouver des automates déterministes équivalents à deux automates donnés et de déterminer leur grammaire régulière associée. Le deuxième exercice demande de construire des automates équivalents et complémentaires à partir de deux automates donnés.

Transféré par

Doucson Seydou Fily Mallé
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

EPI SUP

Théorie des langages


Digital School
2022/2023
Préparatoire 2

TD4 : Série d’exercices n°4

Rappel

3 problèmes qui empêchent l'AFND d'être un AFD :


- La présence de mot de longueur >1.
- La présence de ε.
- Plusieurs sorties (ou aucune) sur les différents symboles de l'alphabet.

NB.
o Pour A, de la transition (ab, S𝑖 , S𝑗 ) ; pour la décomposer on ajoute un nouvel état, S𝑘 et on la remplace
par les transitions (a, S𝑖 , S𝑘 ) et (b, S𝑘 , S𝑗 ).
o Si (ε, S𝑖 , S𝑗 ) ∈ I et S𝑗 est un état final alors S𝑖 deviendra lui aussi état final ;
o Si (ε, S𝑖 , S𝑗 ) et (a, S𝑖 , S𝑘 ) ∈ I alors ajouter la transition : (a, S𝑖 , S𝑘 ) à I. À la fin des ajouts, éliminer la
transition (ε, S𝑖 , S𝑗 ) de I.

Exercice 1 :

Trouver un automate d’états finis déterministe équivalent à A et B :


- A = < V, S, F, S0, I > où V = {0, 1}; S = {S0, S1, S2}; F = {S1, S2}; S0 état initial
I = {(0, S0, S0); (0, S0, S1); (0, S1, S1); (1, S1, S2); (1, S0, S2); (1, S2, S2); (1, S2 , S0) } ;
- B = < V, S, F, S0, I > où V = {a, b}; S = {S0, S1, S2, S3}; F = {S1}; S0 état initial
I = {(a, S0, S0) ; (a , S0 , S1) ; (b , S0 , S2) ; (b , S1 , S2) ; (a , S1 , S3) ; (a , S2 , S2) ; (b , S2 , S1) ;
(b, S2, S3); (a, S3, S1); (b, S3, S2)};
1- Dessiner le diagramme graphique représentant chacun des automates A et B.
2- Déterminer une grammaire régulière à droite équivalente à chacun des automates A et B.
3- Trouver un automate d’état finis déterministe équivalent à A et à B.
Corrigé :

Enseignant (e) : Fatma MLIKA Page 1/1


TD2 : Théorie des langages

Exercice 2 :

Considérons l’automate d’états finis généralisé suivant :


- A = < V, S, F, S0, I > où V = {a, b}; S = {S0, S1, S2, S3, S4, S5}; F = {S5}; S0 état initial
I = {(ε, S0, S1); (ε, S0, S3); (a, S1, S2); (ab, S2, S2); (a, S2, S5); (b, S3, S3); (a, S3, S4);
(a, S4 , S5) } ;
- B = < V, S, F, S0, I > où V = {0,1}; S = {S0, S1, S2, S3}; F = {S3} ; S0 état initial
I = { (00 , S0 , S1) ; (0 , S0 , S2) ; (ε , S1 , S0) ; (ε , S1 , S3) ; (ε , S2 , S1) ; (1 , S2 , S3) ; (0 , S3 , S3) };
1- Construire l’automate simple équivalent à A
2- Construire l’automate simple et déterministe équivalent à B.
3- Construire l’automate qui accepte le complémentaire de L(B).

Enseignant(e) : Fatma MLIKA Page 2/2


TD2 : Théorie des langages

Corrigé :

1-

2-

Enseignant(e) : Fatma MLIKA Page 3/2


TD2 : Théorie des langages

3-

Enseignant(e) : Fatma MLIKA Page 4/2

Vous aimerez peut-être aussi