Examen dInformatique
juin 1999 - durée 3h
Il est recommandé aux étudiants de lire attentivement lensemble du sujet avant de commencer. Les questions sont indépendantes et peuvent être traitées dans nimporte quel ordre. Cependant, les réponses à certaines questions peuvent aider à résoudre celles qui suivent. Tous documents autorisés
Question I Soit A1 l'automate suivant :
I.1. Poser les équations des langages des états de lautomate A1. En déduire un automate A2 plus simple reconnaissant le même langage ;
I.2. Retrouver lexpression régulière R1 la plus simple décrivant le langage de L1 reconnu par A1 ;
I.3. Trouver à partir de A2 une grammaire G1 de type 3 qui engendre L1.
Question II Soit G2 la grammaire sur VT = {a, b} suivante :
S -> A | B
A -> C a | a
B -> b C | a
C -> a b C | epsilon
II.1. Donner le type de cette grammaire ; Simplifier la grammaire (si possible).
II.2. Décrivez le langage L2 engendré par G2 ; Donner son expression régulière R2 ;
II.3. Donner un automate reconnaissant L2. Donner une grammaire G2bis de type 3 à partir de L2.
Question III Soit L3 le langage sur V = {a, b} défini par lexpression régulière suivante :
(ba)*b + a(ba)*
III.1. Donner son automate A3.
III.2. Calculer lintersection L4 entre L3 et L1 ; Préciser et détailler chaque étape du calcul ; Donner une interprétation au résultat obtenu ; Expliquez.
III.3. Que pouvez-vous dire sur lintersection entre L3 et L1 ?