Soit V = {(, )} le vocabulaire utilisé pour toutes les questions.

Question I — Soit L1 le langage composé de l’ensemble des mots qui ont les propriétés suivantes :

• ils commencent toujours par " ( " mais ne se terminent jamais par " ( " ;
• ils contiennent au moins une fois le sous-mot " ( ) ".

Par exemple, les mots suivants appartiennent à L1 :

I.1. Donner un automate d’EF non déterministe acceptant L1 ; déterminiser cet automate ;

I.2. Trouver une expression régulière décrivant ce langage ; préciser la méthode choisie ;

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

Question II — Soit G1 la grammaire suivante :

S --> ( B A B ) | ( ) B ) | ( B ( )

A —-> ( D

B —-> C B C | ( | ) | epsilon

C -—> ( | )

D —-> )

II.1. Donner le type de cette grammaire ;

II.2. Quel est le langage engendré par les règles des lignes 3 et 4 de G1 (avec B comme axiome) ;

II.3. Décrivez le langage engendré par G1 ; quel est le type de ce langage ? Expliquez.

Question III — Soit L2 le langage composé de l’ensemble des mots qui ont les propriétés suivantes :

• la première et la dernière lettre sont différentes ;
• s’ils se terminent par " ) " alors ils doivent contenir " ( ) " ; s’ils se terminent par " ( " alors ils doivent contenir " )( ".

III.1. Trouver un automate d’EF non déterministe acceptant L2 ; donner sa version déterministe ;

III.2. Etendez G1 pour obtenir une grammaire G2 de type 2 qui engendre L2. Expliquez.