Examen d’Informatique
juin 1999 - durée 3h
Il est recommandé aux étudiants de lire attentivement l’ensemble du sujet avant de commencer. Les questions sont indépendantes et peuvent être traitées dans n’importe 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 l’automate A1. En déduire un automate A2 plus simple reconnaissant le même langage ;
I.2. Retrouver l’expression 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 | S A | B S
A —-> C a | epsilon
B —-> a C | epsilon
C —-> a | b
II.1. Donner le type de cette grammaire ; Simplifier la grammaire.
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} composé des mots dont le nombre de a est impair.
III.1. Donner 5 mots de L3 ; Donner son expression régulière R3 et son automate A3.
III.2. Calculer l’intersection L4 entre L3 et L1 ; Préciser et détailler chaque étape du calcul ; Donner une interprétation au résultat obtenu ; Donner 5 mots de L4.
