Théorie des langages : Examen informatique theorie des langages
Télécharger PDFUniversité Mouloud MAMMERI de Tizi-Ouzou
Année universitaire : 2014/2015 Faculté de génie électrique et informatique2 ième année licence – Informatique Département d’informatique
module : Théorie des langages E x a m e n d e R a t t r a p a g e Le 08/04/2015 – Durée 1h 30mn – documents non autorisés
Exercice 1(5 pts)
1) Soit le mot x = ((acb)R .cbaa)R (α
R désigne le reflet miroir de α)
1-1) Donner la chaîne de caractères à laquelle x est égal. (0,5 pt)
1-2) Quelle est la valeur de |x| ? (0,5 pt)
1-3) Donner un préfixe propre de x contenant au moins deux lettres ‘a’. (0,5 pt)
1-4) Donner la sous-chaîne de x qui commence par ‘b’ et se termine par ‘a’. (0,5 pt)
2) Soit V un alphabet ; et w un mot de V
* de longueur n.
2-1) Quel est le nombre de préfixes de w ? (1 pt)
2-2) En supposant que toutes les lettres de w sont différentes, quel est le nombre de sous-chaînes
de w ? (1 pt)
2-3) Donner une condition nécessaire sur n pour que toutes les lettres de w soient différentes. (1 pt)
Exercice 2(8 pts)
Trouver pour chacun des langages suivants une grammaire qui l’engendre :
1) L
1 = { a.b2n .a / n ≥ 0 } ; (2 pts)
2) L
2 = { a
2n b
3m / n ≥ 1, m ≥ 0 } ; (2 pts)
3) L
3 = { a
n b
m c
k / 0 ≤ n ≤ m ≤ k } (2 pts)
4) L
4 = { a
i b
j c
k / k = max(i,j) }. (2 pts)
Exercice 3(7 pts)
Soit L
1 le langage des mots de {a, b}
* tel que dans chaque mot w de L1 , l’une, au moins, des deux
premières lettres de w est un « b » ; et le langage L
2 = {aab, aba}.
1) Construire un automate d’états finis simple qui accepte L1 . (1,5 pts)
2) Construire un automate d’états finis simple qui accepte L2 . (1,5 pts)
3) Construire un automate d’états finis simple qui accepte L
1 L2 . (1,5 pts)
4) Rendre l’automate de 3) déterministe, s’il ne l’est pas. (1,5 pts)
5) Donner l’automate d’états finis qui accepte le complémentaire de L
1 L2 . (1 pt)
Bon courage ! UMMTO / L2 informatique / Théorie des Langages / Rattrapage 2015 / S. Khemliche, H. Djemai, M.S. Habet