Scribd
Importer
15 vues2 pages

TP 5

Le document présente un TP sur les langages et compilateurs, avec plusieurs exercices portant sur la construction et l'analyse d'automates d'états finis. Les exercices incluent la reconnaissance de langages, la création de tables de transition, et la transformation d'automates non déterministes en automates déterministes. Les langages à traiter incluent des combinaisons de lettres et des conditions spécifiques sur leur structure.

Transféré par

noamane ould
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
15 vues2 pages

TP 5

Le document présente un TP sur les langages et compilateurs, avec plusieurs exercices portant sur la construction et l'analyse d'automates d'états finis. Les exercices incluent la reconnaissance de langages, la création de tables de transition, et la transformation d'automates non déterministes en automates déterministes. Les langages à traiter incluent des combinaisons de lettres et des conditions spécifiques sur leur structure.

Transféré par

noamane ould
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

TP 5

INF4061– LANGAGES & COMPILATEURS


Responsable Module: Oussama SMIMITE
Niveau: 4ème Année Année: 2022/2023
Filière: G. Informatique Session: 2 – Hiver 2023

EXERCICE 1 :

1. Quel est le langage reconnu par l’automate suivant

2. Écrire la table de transition de l’automate suivant. Quel est le langage reconnu ?

EXERCICE 2 :

Pour chacun des langages suivants, construire un automate d’états finis qui l’accepte :
a) L1 = {w  {a, b, c}* / w contient au moins une occurrence de la lettre ‘a’ } ;
b) L2 = { w  {a, b}* / w = anbma n, m ≥ 1 } ;
c) L3 = { w  {a,b}* / w = ban n ≥ 1} ;
d) L4 = { w  {a, b}* / |w| est divisible par 6 } ;
EXERCICE 3 :

Etant donné les automates d’états finis non déterministes :


a) A = < V , S , F , S0 , I > où V = {0, 1} ; S = {S0 , S1 , S2} ; F = {S1 , S2} ; S0 état initial
I = { (0 , S0 , S0) ; (0 , S0 , S1) ; (0 , S1 , S1) ; (1 , S1 , S2) ; (1 , S0 , S2) ; (1 , S2 , S2) ; (1 , S2 , S0) } ;
b) B = < V , S , F , S0 , I > où V = {a, b} ; S = {S0 , S1 , S2 , S3} ; F = {S1} ; S0 état initial
I = { (a , S0 , S0) ; (a , S0 , S1) ; (b , S0 , S2) ; (b , S1 , S2) ; (a , S1 , S3) ; (a , S2 , S2) ; (b , S2 , S1) ;
(b , S2 , S3) ; (a , S3 , S1) ; (b , S3 , S2) } ;
1. Dessiner le diagramme graphique représentant chacun des automates A et B.
2. Trouver un automate d’états finis déterministe équivalent à A et à B.

EXERCICE 4 :

Soit L1 le langage des mots de {a, b}* contenant un nombre impair de lettres «a» ; et L2 = {aa, ab}.

• Construire un automate d’états finis simple qui accepte L1

• Construire un automate d’états finis simple qui accepte L2.

EXERCICE 5 :

Rendre l’automate suivant déterministe.

Vous aimerez peut-être aussi