Scribd
Importer
4 vues2 pages

ExamenTHL 2018

Le document présente un examen de théorie des langages, comprenant des exercices sur les automates d'états finis, les grammaires régulières et les expressions régulières. Les étudiants doivent résoudre des problèmes liés à la reconnaissance de langages, à la génération de grammaires et à l'écriture aérée des nombres. Les exercices abordent également des langages spécifiques et des dates valides.

Transféré par

Imen Amrous
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
4 vues2 pages

ExamenTHL 2018

Le document présente un examen de théorie des langages, comprenant des exercices sur les automates d'états finis, les grammaires régulières et les expressions régulières. Les étudiants doivent résoudre des problèmes liés à la reconnaissance de langages, à la génération de grammaires et à l'écriture aérée des nombres. Les exercices abordent également des langages spécifiques et des dates valides.

Transféré par

Imen Amrous
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

USTHB 27 Mai 2018

Faculté d’Electronique et d’Informatique


Département d’Informatique (Sections L2 ACAD A+C)

Examen de Théorie des Langages

Exercice 1 :

Soit le langage L1 reconnu par l’automate d’états finis suivant :

q0 aba
q1
/a
q2 a

ab b

q3

1) Trouver l’automate d’états finis simple déterministe équivalent à cet automate.


2) Déduire de l'automate déterministe obtenu la grammaire régulière droite générant L1.

Soit le langage FG(L) défini comme suit :


FG(L) ={v / v {a,b}* u {a,b}* et vuL }
3) Déduire une grammaire régulière droite générant FG(L1)
4) De manière générale, soit un langage L généré par une grammaire G=T, N, S, P où toutes les
règles de productions sont de la forme A→wB ou A→w avec A, B N et wT{}. Dans ce cas,
donner la grammaire qui génère le langage FG(L) à partir de celle qui génère L.

Exercice 2 :

Trouver les expressions régulières qui dénotent les langages suivants :


1) Les mots sur l’alphabet {a,b} tel que la troisième lettre à partir du début est a et la troisième lettre à
partir de la fin est b.
2) Les mots sur l'alphabet {a, b, c} qui commencent par a si le nombre de a est impair, par b sinon.
3) Les mots sur l'alphabet {a, b,c} qui ne contiennent pas au moins un symbole de l'alphabet.
4) Toutes les dates valides incluses entre le début du deuxième semestre (04/02/2018) et le jour de
l’examen (27/05/2018). Une date est exprimée sous la forme JJ/MM/AAAA.

Exercice 3 :

On s'intéresse à l'écriture aérée des grands nombres avec l'utilisation du caractère "_" non significatif
entre les chiffres.
A) Le langage Ada autorise une écriture "aérée" des constantes entières avec l'utilisation du caractère "_"
non significatif entre des chiffres du nombre. Nous supposons que tous les chiffres sont significatifs.
Par exemple : 1234 ou 1_234 ou 12_34 ou 1_23_4 ....

1) Donner un automate d'états finis reconnaissant les constantes entières Ada.


USTHB 27 Mai 2018
Faculté d’Electronique et d’Informatique
Département d’Informatique (Sections L2 ACAD A+C)

Examen de Théorie des Langages

B) Le monde anglo-saxon accepte l'écriture aérée des grands nombres avec des séparateurs (blanc,
point ou virgule) pour les milliers et les puissances de [Link] considérons le langage des
nombres entiers naturels ne contenantque le séparateur "_" uniquement pour les milliers et les
puissances de milliers. De plus, tous les chiffres sont significatifs. Par exemple 1_200_507 ou
31_260 ou 124_200 ou 142 ou 24 ou 8 ou 124_200_254…..
1) Donner une grammaire générant ce langage.
2) Donner un automate d'états finis le reconnaissant.

Exercice 4 :

Soit le langage L suivant :


L={a2nwbm/n,m≥0, w {0,1}* et |w|=n+2m}
1) Donner une grammaire générant le langage L
2) Donner un automate à pile par état final reconnaissant le langage L.

Vous aimerez peut-être aussi