Département : Informatique
Spécialité: Informatique, Niveau : Licence 2
Faculté des
Examen de Théorie des Langages Mathématiques et de
l'Informatique
NOM : PRENOM : Groupe
Exercice 1. ( 6 pts)
1) Déterminer les facteurs, les préfixes et les suffixes du mot u = abaab.
• Préfixes(u) = { ε , a, ab, aba, abaa, abaab} (0,5 pt)
• Suffixes(u) = { ε , b, ab, aab, baab, abaab} (0,5 pt)
• Facteures(u)= { ε , a, b, ab, ba, aa, aba, baa, aab, abaa, baab, abaab} (0,5 pt)
2) Calculer le produit L.M pour les cas suivants :
• L = {b, aba, bab} et M = { ε }, donc L.M = L (0,5 pt)
• L = {b, aba, bab} et M = ∅, donc L.M = ∅ (0,5 pt)
• L = {a,b}* et M = { aa, bb }, donc L.M = tous les mots qui se terminent par aa ou bb
(0,5 pt)
3) On considère l’alphabet ∑ = {a,b}, et les langages L1 et L2 suivants :
L1 = {anbn | n ≥ 0} et L2 = {anbm | n ≥ m ≥ 0}
Calculer :
• L1 ∪L2 = L2 (1 pt)
• L1 ∩ L2 = L1 (1 pt)
• L1.L2 = { anbnapbm | n ≥ 0, p ≥ m ≥ 0} (1 pt)
Responsable du module : Nouioua Farid Année Universitaire : 2019-2010 Page 1/3
NOM : PRENOM : Groupe
Exercice 2. (8 pts)
Pour chacun des automates (A1) et (A2) suivants :
1) Dire s’il est déterministe ou pas (0,75 + 0,75)
2) Dire s’il est complet ou pas. (0,75 + 0,75)
3) Donner le langage qu’il reconnaît (1,5 + 0,5)
4) S’il n’est pas complet, donner l’automate complet équivalent. (1,5 + 1,5)
0,1 0,1 (A2) a,b
0 1
(A1)
1 0
A B C a,b a,b
2
Déterministe ? OUI / NON Déterministe ? OUI / NON
Complet ? OUI / NON Complet ? OUI / NON
Langage reconnu : (il suffit de donner une des trois
Langage reconnu : (il suffit de donner une des deux réponses suivantes)
réponses suivantes)
L(A2) = Tous les mots sur l’alphabet {a, b} qui dont la
L(A1) = Tous les mots sur l’alphabet {0, 1} qui longueur est multiple de 3.
contiennent le facteur 10.
L(A2) = { w ∈ {0, 1}* | |w| est multiple de 3}
L(A1) = { w10w’ | w, w’ ∈ {0, 1}*}
L(A2) = { w ∈ {0, 1}* | |w| = 3k avec k ≥ 0}
Automate complet équivalent : Automate complet équivalent :
0,1 0,1 Déjà complet
1 0
A B C
P
0,1
Responsable du module : Nouioua Farid Année Universitaire : 2019-2010 Page 2/3
NOM : PRENOM : Groupe
Exercice 2. (6 pts)
1) Trouver un automate d’états finis ayant trois états pour le langage L1 qui contient tous les
mots sur l’alphabet Σ = {a, b} qui se terminent par ba.
Réponse. (3 pts)
b
a
b a
0 1 2
2) Même question pour le langage L2 qui contient tous les mots sur l’alphabet Σ = {a, b} qui ne
contiennent pas le facteur bbab. (l’automate demandé possède quatre états)
Réponse. (3 pts)
b
a
b b a
0 1 2 3
Responsable du module : Nouioua Farid Année Universitaire : 2019-2010 Page 3/3
