Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Université Dr. Yahia Fares de Médéa 2019/2002 Faculté des sciences Départemen

1 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. Exercice 4 Soit A un AEF généralisé, représenté par le graphe suivant : 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). q0 a ba q1 ε b b q2 q3 a a a uploads/Science et Technologie/ thl-td3.pdf