Les énoncés des deuxième et troisième exercices de l’épreuve optionnelle d’informatique du concours commun Centrale, cuvée 1998. Dans l’exercice II, j’ai éliminé la fastidieuse présentation des automates finis, et corrigé la coquille de l’énoncé; pour dessiner l’automate, j’ai utilisé le paquetage autograph, écrit par Paul Gastin; on peut le trouver à la page personnelle de Paul:

               http://www.liafa.jussieu.fr/~gastin

Exercice II

II.B - Soit l’alphabet A = {a, b, c}. Montrer que l’automate déterministe, donné par le graphe ci-dessous, reconnaît le langage

L_{2} = {u · c · u | u ∈ {a, b}^{∗}, |u| = 2}

[figure: e_{ε}; e_{a}; e_{b}; e_{aa}; e_{ab}; e_{ba}; e_{bb}; f_{aa}; f_{ab}; f_{ba}; f_{bb}; f_{a}; f_{b}; f_{ε}; a; b; a; b; a; b; c; c; c; c; a; a; b; b; a; b]

Dans les deux questions suivantes, on veillera à justifier la validité des constructions proposées.

II.C - Généralisation: soit n ⩾ 1 un entier, construire un automate déterministe qui reconnaît le langage:

L_{n} = {u · c · u | u ∈ {a, b}^{∗}, |u| = n}

Quel est, en fonction de n, le nombre d’états de cet automate?

II.D - Construire un automate non déterministe, qui reconnaît le langage suivant:

L′_{n} = {v · c · w | ∃v_{1}, v_{2}, w_{1}, w_{2}, u ∈ {a, b}^{∗}, |u| = n, v = v_{1} · u · v_{2}, w = w_{1} · u · w_{2}}

Donner le nombre d’états de cet automate en fonction de n. II.E - Donner le graphe d’un automate reconnaissant L′_{2} (cas où n = 2).

Soit A un automate fini non déterministe reconnaissant L′_{n}.

II.F - Montrer que les états par lesquels passe l’automate A lorsqu’il reconnaît un mot de longueur 2n + 1 sont tous distincts.

II.G - Montrer que le nombre d’états accessibles de A est au moins 2^{n+1} −1.

II.H - Montrer que tout automate déterministe ou non déterministe qui reconnaît L′_{n} a au moins 2^{n+2} − 2 états.

II.I - Donner une expression rationnelle associée à L′_{2}. II.J - Donner une expression rationnelle associée à A^{∗} − L′_{1}.

Exercice III On appelle ici expression booléenne toute expression construite avec les

variables booléennes a, b, …, z, les connecteurs binaires ∨ (OU) et ∧ (ET), le connecteur unaire ¬ (NON) et les deux connecteurs 0-aires (c’est-à-dire les constantes booléennes) T (VRAI) et F (FAUX).

III.A - Montrer que toute expression booléenne est équivalente à une expression utilisant uniquement ∧ et ¬ comme connecteurs.

III.B - Soit le connecteur ternaire G(a, b, c) défini par :

G(a, b, c) = (¬(a) ∧ b ∧ c) ∨ (a ∧ (¬(b))) ∨ (¬(b) ∧ ¬(c))

Montrer que toute expression booléenne est équivalente à une expression utilisant uniquement G comme connecteur.

III.C - Soit le connecteur binaire − défini par b−a = (¬(a)∧b). Montrer que toute expression booléenne est équivalente à une expression utilisant uniquement − et T comme connecteurs.

III.D - Toute expression booléenne est-elle équivalente à une expression utilisant uniquement − comme connecteur?