sujet THL 2016 2017 .pdf


Nom original: sujet_THL_2016_2017.pdfAuteur: digitec

Ce document au format PDF 1.5 a été généré par Microsoft® Office Word 2007, et a été envoyé sur fichier-pdf.fr le 24/01/2018 à 00:03, depuis l'adresse IP 105.101.x.x. La présente page de téléchargement du fichier a été vue 220 fois.
Taille du document: 470 Ko (1 page).
Confidentialité: fichier public

Aperçu du document


Ministère de l’Enseignement Supérieur et de la Recherche Scientifique
Université Alger1 – Benyoucef Benkhadda
Faculté des Sciences
Département Mathématiques Informatique
Nature : ETLD
Module : THL
Durée : 1h30mn
Date : 28/01/2017
Filière : L2-INF/S3
Exercice 1 (cours) (3 pts)
Transformer la grammaire suivante en Forme Normale de Chomsky (FNC)
- G1({a,b}, {S,A,B,C,D},S, P) avec :
P={ SABCD ; AaA | ; BAb ; CA |aaB ; D aA | B })
Exercice 2 (5 pts)
Soit l’expression suivante :
définie sur l’alphabet X={a, b, c}.
1- Donnez l’automate T de Thompson associé.
2- Donnez un automate A non-déterministe et sans -transitions correspondant.
3- Donnez l’automate du langage complémentaire qu’elle représente.

Exercice 3 (6 pts)
Soit G la grammaire hors-contexte (algébrique) définie sur {a, b}*par les productions suivantes :
S  AbB ; A aA | ; B aB | bB |
1- Donner une dérivation à gauche et une dérivation à droite pour chacun des mots suivants:
w1 = a2bab, w2 = ba2b et w3 = a3b2. Dresser l’arbre de dérivation pour chaque mot wi, i = 1,2,3.
2- Déterminer L(G), le langage engendré par G.
3- G est elle ambiguë? Justifier.

Exercice 4 (6 pts)
1- Trouver les grammaires qui engendrent les langages suivants :
2- En déduire la grammaire de
3- Construire l’automate à pile qui reconnait le langage .

Bon Courage


Aperçu du document sujet_THL_2016_2017.pdf - page 1/1



Télécharger le fichier (PDF)

sujet_THL_2016_2017.pdf (PDF, 470 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


td2
serie thl 3 2017 2018
correction td2
sujet thl 2016 2017
corrige serie3 thl 2017 2018
etcd l2 2017 2018 thl

Sur le même sujet..