Scribd
Importer
79 vues2 pages

THL TD3

L'exercice contient 6 exercices portant sur les automates à états finis. Les exercices demandent de représenter des automates sous forme matricielle et graphique, de reconnaître des mots, de donner des langages reconnus et des automates équivalents.

Transféré par

yohace7407
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
79 vues2 pages

THL TD3

L'exercice contient 6 exercices portant sur les automates à états finis. Les exercices demandent de représenter des automates sous forme matricielle et graphique, de reconnaître des mots, de donner des langages reconnus et des automates équivalents.

Transféré par

yohace7407
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é Dr.

Yahia Fares de Médéa 2019/2002


Faculté des sciences
Département de mathématique et informatique
2ème année Licence informatique
Module : Théorie des langages

Série d’exercices 3

Exercice 1
Soit A=(X,Q,q0,δ,F) un automate d’état fini défini par: X={a,b},Q={q0,q1,q2,q3},F={q2,q3},
δ(q0,a)=q1, δ(q0,a)=q3 , δ(q0 ,b)=q2 , δ(q1, a)=q2 , δ(q1, b)=q1 , δ(q2,b)= q3, δ(q3,a)= q3.

1. Donner les représentations : matricielle et graphique de A.

2. Est-ce que les mots suivants : w1=abab, w2=ba, w3=abb sont-ils reconnus par A ?

3. Donner des mots L(A) de longueur=1 à 4.

Exercice 2
Donner la représentation graphique des AEF simples reconnaissant les langages suivants :

- L0={aa, aba, aab, bab}


- L1={w{a,b} | w =abn , n ≥ 1}
- L2={w{a,b,c} |w commence par a, se termine par c et contient au moins un b}
- L3={w{a,b} | w = ambn ; n ≥ 0, m ≥ 0}
- L4={w{0,1} | w=1(01)n0, n≥0}
- L5={w{a,b} | |w|a  0[3]}
- L6 = { w{a,b} | |w|a et |w|b sont pairs }

Exercice 3
Etant donné A=(X,Q,q0,δ,F) un AEF simple défini comme par X={a, b}, Q={q0, q1, q2, q3}, F={q1},
δ(q0,a)=q3, δ(q0,b)= q1, δ(q0,b)=q3, δ(q1,a)=q2 , δ(q1,b)=q3 , δ(q2,a)= q2, δ(q2,b)= q3, δ(q3,a)= q1 ,
δ(q3,a)=q2 , δ(q3,b)=q3.

1. Tracer le graphe de A.
2. Déterminer une grammaire régulière droite équivalente à A.
3. Trouver l’AEF déterministe correspondant à A.

1
Exercice 4
Soit A un AEF généralisé, représenté par le graphe suivant :

b
a
ba a
q0 q1
a q3
ε
a b
q2

1. Construire l’AEF simple équivalent de A.

Exercice 5
Soit A l’AFD représenté par le graphe ci-dessous :

1. Donner l’automate minimal de A.

Exercice 6
Soit G=(T, N, S, P) une grammaire définie par
T= {a, b} , N= {S, A, B} ,
P = { S → aS/bA/ , A → bA/bB ,
B → aB/a }.
1. Construire l’AEF simple qui accepte L(G).

Vous aimerez peut-être aussi