Question I — Soit L1_n le langage sur V = {a, b} composé de l’ensemble des mots sur V* qui contiennent le sous-mot " abn ".Par exemple, les mots suivants appartiennent à L1₂ :

I.1. Trouver une expression régulière simple de L1₂. Donner un automate d’EF non déterministe acceptant L1₂ et le déterminiser et le simplifier (si nécessaire).

I.2. En déduire une Expression Régulière Non Ambigüe (ERNA) de L1₂ (détailler le calcul).

I.3. Trouver une forme générale d’ERNA pour L1_n. Donner une ERNA pour L1₁, L1₃, L1₄.

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

A —-> a A | b A | a B

B —-> b C

C —-> b D D —> b E

E —-> a E | b E | a A | b A | epsilon

II.1. Donner le type de cette grammaire. Quel est le langage L engendré par G ? Trouver son expression régulière (expliquez).

II.2. Donner une grammaire G’ plus simple et non ambigüe équivalente à G (justifiez).

II.3. Donner une grammaire G2 de L2 qui est l’union entre L et son mirroir (en utilisant l’automate de L et son mirroir).

Question III — Soit L3_n le langage défini par la forme d’automate suivante :

III.1. Dans le cas où n = 2, montrer que l’ERNA de L3₂ est : a*b(b+ab)*aa(a+b)*. A quoi correspond L3_n par rapport à L1_n ?

III.2. Donner une expression régulière de L4_1-1 intersection entre L1₁ et L3₁ (expliquez votre calcul ou votre le raisonnement). Quels sont, parmis les mots exemples donnés en I ceux qui appartiennent à L4_1-1 (expliquez).

III.3. Donner une machine de Turing reconnaissant L4_1-1. Bien préciser les définitions et le fonctionnement de cette machine.