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

juin 1998 - 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 défini par la grammaire G1 suivante :

(1) S --> A R | R

(2) A --> S a | a

(3) R --> T | epsilon

(4) E --> T + T | T

(5) T --> F T | F

(6) F --> ( E ) | E* | b

avec V = {a, b, +, *, (, )}

I.1. Soit LERb (Langage d’Expression Régulières sur b) le langage L1(E) défini par la sous-grammaire de G1 dont E est l’axiome (cad les règles des lignes 4, 5 et 6). Donnez 3 mots de LERb ; décrivez informellement le langage LERb. Idem pour L1(T).

I.2. Donnez 3 mots de L1. ; décrivez informellement le langage L1 ; rendez G1 e-libre ; Supprimez la récursivité gauche dans G1.

Question II — On nomme L1(n) l’ensemble des mots de L1 obtenu en passant n fois par une des règles de la ligne 2 de G1 (cad les règles A --> S a | a).

II.1. À quel ensemble L1(n) appartiennent les mots suivants :

b*a(b+bb)*, (bb + bbb)aba(bb)*, b*, abab*abab*b*a, aaa, epsilon

II.2. Donnez 3 mots (différents de la question II.1.) pour chacun des langages suivants :

L1(0), L1(1), L1(2) et L1(5)

II.3. On peut considérer chaque L1(n) comme un ensemble (infini) d’expressions régulières ou encore correspondant à une famille de langages réguliers. Décrivez informellement L1(0), L1(1), L1(2) et L1(5). À quoi correspond L1(n) ?

Question III — On défini une nouvelle grammaire G*, à partir de G1, en ajoutant la règle :

(0) F --> R ( S )* et avec F comme nouvel axiome (source) de G*.

Comme pour L1, on nomme L*(n) l’ensemble des mots de où l’on passe n fois par une des règles de la ligne 2 de G* (cad les règles A --> S a | a).

De plus, on considére les mots er2 = b*(ab*ab*)* et er3 = b*(ab*ab*ab*)*

III.1. Ecrivez G*. Quels langages réguliers sont décrits respectivement par er2 et par er3 ?
À quel langage L*(n) appartiennent respectivement er2 et er3 ?

III.2. Décrivez informellement L*(0), L*(1), L*(2) et L*(5). À quoi correspond L*(n) ?

III.3. Calculez er2 er3. Décrivez informellement le langage representé par er2 er3. Que pouvez-vous dire sur tout wn wp où wn L*(n) et wp L*(p) ?