Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



serie THL 3 2017 2018 .pdf


Nom original: serie_THL_3_2017_2018.pdf
Auteur: Touil

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 23/01/2018 à 09:08, depuis l'adresse IP 105.99.x.x. La présente page de téléchargement du fichier a été vue 220 fois.
Taille du document: 637 Ko (2 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Alger 1 - Faculté des Sciences
Département Mathématiques et Informatique
Module : Théorie des langages
Année Universitaire : 2017-2018

Filière : Informatique.
Semestre : S3
Série N° 3 : Automates à pile

Exercice 1 : (sujet d’examen 2016/2017)
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 2 :
-Définir un AP reconnaissant le langage L = {anbn / n ≥ 0}
Donner la valeur de la pile pour chaque nouvelle lettre lue dans le mot aaabbb et vérifier qu’il est accepté.
Même question pour le mot abab, est-il accepté ?
-Donner la valeur de la pile pour chaque nouvelle lettre lue dans le mot aaabbabb par l’AP suivant :
(a,-) //empiler(a)
1
(b,a) // dépiler

préfixe lu = a, pile = a
préfixe lu = aa, pile = aa, etc.
En déduire que le mot aaabbabb est accepté.
Même question pour le mot abba. Est-il accepté ?
En déduire le langage reconnu par l’automate.
Exercice 3 :
Définissez les automates à pile reconnaissants les langages suivants :
1- L1={ai(ab)ick / i, k >0}
2- L2={wcwR / w {a,b}* }
3- L3 = { ai bjci , i ≥ 0 } ;
Exercice 4 :
Donner le langage reconnu par l’automate A<X,Y,S, S0, F, II, #> avec:
X = {a, b, c}, Y = X, S = { S0, S1, S2, Sf}, F= {Sf} et II :
# S0 a → # aS0
# S0 b → # b S0
# S0 c → # S2
aS0 a → aaS0
a S0 b → ab S0
bS0 a → ba S0
b S0 b → bb S0
a S0 c → a S1
b S0 c → b S1

a S1 a → S1
b S1 b → S1
b S1 a → S2
a S1 b → S2
a S2 b → S2
a S2 a → S2
b S2 b → S2
b S2 a → S2
# S2 → # Sf

Page 1 sur 2

Exercice 5 :
Définir un AP reconnaissant les expressions bien parenthésées. On pourra prendre X = {(, ), a} où a symbolise
une lettre qui n’est pas une parenthèse. Exemple : a(a(aa)(a))a sont OK mais ni a()a, ni a(a(aa)(a)a, ni
a(a(aa)(a))a)a.
Exercice 6 :
Soit l’alphabet X={a,b}
Ecrire la grammaire de chacun des langages suivants et montrer que se sont des langages algébriques :
1- L1={anb / n>=0}
2- L2={anbn /n>=0}
3- L3={anbp / n > p>=0 }
Exercice 7 :
Soit la grammaire définit comme suit : G<{a,b}, {S}, S, {SaS |aSbS | }>
1- Cette grammaire est-elle ambigüe ? montrer que le mot aab possède deux :
a- Arbres de dérivations
b- Dérivations à droite
c- Dérivations à gauche
2- Trouver une grammaire non ambigüe pour le langage L(G)
Exercice 8 :( sujet d’examen 2016/2017)
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 9 :( sujet d’examen 2016/2017)
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 .
Exercice 10 : (sujet d’examen 2016/2017)
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 })

Page 2 sur 2


serie_THL_3_2017_2018.pdf - page 1/2
serie_THL_3_2017_2018.pdf - page 2/2

Documents similaires


Fichier PDF sujet thl 2016 2017
Fichier PDF td2
Fichier PDF examen thl 2010
Fichier PDF serie thl 3 2017 2018
Fichier PDF notionsfondamentamles 2010 2011
Fichier PDF etcd l2 2017 2018 thl


Sur le même sujet..