Scribd
Importer
403 vues1 page

THL Rattrapage 2017-18

L'examen porte sur la théorie des langages formels. Il contient trois exercices: le premier concerne les langages réguliers et non réguliers, le deuxième demande de trouver des grammaires pour différents langages et le dernier traite des automates à états finis.

Transféré par

Emna Kanzari
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
403 vues1 page

THL Rattrapage 2017-18

L'examen porte sur la théorie des langages formels. Il contient trois exercices: le premier concerne les langages réguliers et non réguliers, le deuxième demande de trouver des grammaires pour différents langages et le dernier traite des automates à états finis.

Transféré par

Emna Kanzari
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é Mouloud MAMMERI de Tizi-Ouzou Année universitaire : 2017/2018

Faculté de génie électrique et informatique 2 année licence – Informatique


ième

Département d’informatique module : Théorie des langages

Examen de rattrapage
le 10/04/2018 – Durée 1h 30mn – documents non autorisés

EXERCICE 1 : (6 pts)
Soit V un alphabet fini. On désigne par 𝒫(V*) l’ensemble des parties de V*.
On définit la fonction C : 𝒫(V*)  𝒫(V*) comme suit :
pour tout langage L défini sur V, on a : C(L) = { w ∈ V* / ∃ u ∈ L tel que w = u.u }.
1) Soit L = { (ab)n / n ≥ 0 } et L1 = C(L).
1-1) Caractériser L1 (i.e donner la propriété vérifiée par les mots de L1). (1 pt)
1-2) À l’aide du théorème de Nerode, montrer que L1 est régulier. (1 pt)
2) Soit L = { [Link] / n ≥ 0 } et L2 = C(L).
2-1) Caractériser L2. (1 pt)
2-2) À l’aide du théorème de Nerode, montrer que L2 n’est pas régulier. (1 pt)
3) Déterminer L1.L2 et L1 ∩ L2. (1 pt)
4) Soit L un langage quelconque. Quelle relation y a-t-il entre C(L) et L.L ? (1 pt)

EXERCICE 2 : (8 pts)
I) Trouver :
I-1) une grammaire de type 3 pour L1 = langage des mots de {a, b, c}* ; où dans chaque mot de L1,
chaque lettre de rang pair est un «a» (les lettres sont numérotées à partir du n° 1) ; (1,5 pts)
I-2) une grammaire de type 2 pour L2 = { [Link].a / n ≥ 0 } ; (1,5 pts)
I-3) une grammaire de type 1 pour L3 = { u.u / u ∈ {0, 1}* } ; (1,5 pts)
I-4) une grammaire de type 0 pour L4 = { [Link]×m / n, m ≥ 0 }. (1,5 pts)
II) Trouver un automate d’états finis simple pour le langage L1 de I-1) de cet exercice. (2 pts)

EXERCICE 3 : (6 pts)
Soit A l’automate d’état fini simple défini par : < V, S, F, S0, I > ; où :
V = {a, b, c}, S = { S0, S1, S2, S3, S4, S5}, F = {S4, S5} et I = {(a, S0, S1), (a, S0, S2), (a, S1, S1),
(b, S1, S3), (c, S2, S3), (a, S3, S3), (a, S3, S4), (c, S3, S5), (b, S4, S4)}.
1) Dessiner le graphe représentant l’automate A. (1 pt)
2) Construire un automate d’états finis partiellement généralisé qui accepte (L(A))R. (1 pt)
3) Construire un automate d’états finis partiellement généralisé qui accepte (L(A))+. (1 pt)
4) Construire l’automate déterministe équivalent à A. Dessiner son graphe. (2 pts)
5) À partir de l’automate A, trouver l’expression régulière qui dénote L(A). (1 pt)

Bon courage !

UMMTO / L2 informatique / Théorie des Langages / Rattrapage 2018 / M.S. Habet, C. Cherifi, N. Otmani, F. Bouhatem

Vous aimerez peut-être aussi