Université de Montpellier II — DEUG MASS — niveau 1 — période 1 — Informatique

Université de Montpellier II – DEUG MASS – niveau 1 – période 1 – Informatique – UE1603ME

Examen d’Informatique

janvier 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 L1 le langage sur V = {a, b} composé de l’ensemble des mots qui ont les propriétés suivantes :

ils commencent par une répétition (éventuellement nulle) de " ab " ;
ils se terminent par une répétition (éventuellement nulle) de " ba " .

Par exemple, les mots suivants appartiennent à L1 :

" ab ", " abbaba ", … " ababbaba ", " bababa"

I.1. Donner l’expression régulière de L1 ; construire de façon systématique (et astucieuse) l’automate A(L1) ;

I.2. Retrouver une expression régulière de L1 à partir de A(L1) ; préciser la méthode choisie ;

I.3. Trouver une grammaire G1 de type 3 qui engendre L1.

Question II – Soit G2 la grammaire sur V_T = {a, b} suivante :

1 S --> A B | A S B

2 A --> C A |

3 B --> B D |

4 C --> E a

5 D --> a E

6 E --> b

II.1. Donner le type de cette grammaire ; quels sont les langages L2(A) (resp. L2(B)) engendrés à partir de A (resp. B) ? Simplifier la grammaire (par exemple-libre, moins de règles).

II.2. Décrivez le langage L2 engendré par G2 (axiome S) ; quel est le type de ce langage ?

II.3. Calculer le langage L3 = L1 L2 ; expliquer chaque étape du calcul.

Question III – Soit L4 le langage sur V = {a, b} composé des palindromes de L1. On rappelle qu’un palindrome est un mot égal à son miroir w = w~.

III.1. Donner 5 mots de L4 ; Avons-nous e L4 ? Quelle est la forme générale de w L4 ?

III.2. Donner une machine de Turing T(L4) qui accepte les mots de L4. Vous pouvez utiliser {a, b, 0, *, V, F} comme symboles ; les conditions initiales et finales doivent être précisées ; bien expliquer la fonctionnement de T(L4) et commenter les transitions.