\documentclass[10pt,a4paper]{article}\nofiles

\usepackage[applemac]{inputenc}
\usepackage{epic,autograph}
\usepackage{amsfonts,amssymb}

\begin{document}

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

\begin{center}
\verb$http://www.liafa.jussieu.fr/~gastin$
\end{center}

\bigskip

\textbf{Exercice II}

\textbf{II.B -}
Soit l'alphabet $A=\{a,b,c\}$. 
Montrer que l'automate d{\'e}terministe, donn{\'e} par le graphe ci-dessous, 
reconna{\^\i}t le langage 

\[
 L_2 = \bigl\{ u \cdot c \cdot u \bigm| u \in \{a,b\}^*, |u|=2 \bigr\}
\]

\begin{center}
\begin{picture}(80,70)(0,0)
\put(0,0){\framebox(80,70){}}
\thinlines

\letstate A=(40,60) \drawinitialstate[t](A){$e_\varepsilon$}
\letstate B=(20,50) \drawstate(B){$e_a$}
\letstate C=(60,50) \drawstate(C){$e_b$} 
\letstate D=(10,40) \drawstate(D){$e_{aa}$}
\letstate E=(30,40) \drawstate(E){$e_{ab}$}
\letstate F=(50,40) \drawstate(F){$e_{ba}$}
\letstate G=(70,40) \drawstate(G){$e_{bb}$}
\letstate H=(10,30) \drawstate(H){$f_{aa}$}
\letstate I=(30,30) \drawstate(I){$f_{ab}$}
\letstate J=(50,30) \drawstate(J){$f_{ba}$}
\letstate K=(70,30) \drawstate(K){$f_{bb}$}
\letstate L=(20,20) \drawstate(L){$f_a$}
\letstate M=(60,20) \drawstate(M){$f_b$} 
\letstate N=(40,10) \drawrepeatedstate(N){$f_\varepsilon$}

\drawtrans[l](A,B){$a$}
\drawtrans[r](A,C){$b$}
\drawtrans[l](B,D){$a$}
\drawtrans[r](B,E){$b$}
\drawtrans[l](C,F){$a$}
\drawtrans[r](C,G){$b$}
\drawtrans[l](D,H){$c$}
\drawtrans[l](E,I){$c$}
\drawtrans[l](F,J){$c$}
\drawtrans[l](G,K){$c$}
\drawtrans[r](H,L){$a$}
\drawtrans[r](I,M){$a$}
\drawtrans[l](J,L){$b$}
\drawtrans[l](K,M){$b$}
\drawtrans[r](L,N){$a$}
\drawtrans[l](M,N){$b$}
\end{picture}
\end{center}
\bigskip

Dans les deux questions suivantes, on veillera {\`a} justifier 
la validit{\'e} des cons\-truc\-tions propos{\'e}es.
\smallskip

\textbf{II.C -}
G{\'e}n{\'e}ralisation: soit $n \geqslant 1$ un entier, construire 
un automate d{\'e}ter\-mi\-niste qui reconna{\^\i}t le langage:

\[
 L_n = \bigl\{ u \cdot c \cdot u \bigm| u \in \{a,b\}^*, |u|=n \bigr\} 
\]

Quel est, en fonction de $n$, le nombre d'{\'e}tats de cet automate?
\smallskip

\textbf{II.D -}
Construire un automate non d{\'e}ter\-mi\-niste, qui reconna{\^\i}t le langage 
suivant:

\[
 L_n' = \bigl\{ v \cdot c \cdot w \bigm| 
 \exists v_1, v_2,w_1,w_2,u \in \{a,b\}^*, \\ |u|=n, v=v_1 \cdot u \cdot v_2, 
 w = w_1 \cdot u \cdot w_2 \bigr\} 
\]

Donner le nombre d'{\'e}tats de cet automate en fonction de $n$.
\smallskip

\textbf{II.E -}
Donner le graphe d'un automate reconnaissant $L_2'$ (cas o{\`u} $n=2$).
\smallskip

\medskip
Soit $\cal A$ un automate fini non d{\'e}terministe reconnaissant $L_n'$.
\medskip

\textbf{II.F -}
Montrer que les {\'e}tats par lesquels passe l'automate $\cal A$ 
lorsqu'il reconna{\^\i}t un mot de longueur $2n+1$ sont tous distincts.
\smallskip

\textbf{II.G -}
Montrer que le nombre d'{\'e}tats accessibles de $\cal A$ est au moins 
$2^{n+1}-1$.
\smallskip

\textbf{II.H -}
Montrer que tout automate d{\'e}terministe ou non d{\'e}terministe qui 
reconna{\^\i}t $L_n'$ a au moins $2^{n+2}-2$ {\'e}tats.
\smallskip

\textbf{II.I -}
Donner une expression rationnelle associ{\'e}e {\`a} $L_2'$.
\smallskip

\textbf{II.J -}
Donner une expression rationnelle associ{\'e}e {\`a} $A^* - L_1'$.
\smallskip

\bigskip

\textbf{Exercice III}
\smallskip

On appelle ici expression bool{\'e}enne toute expression construite 
avec les varia\-bles bool{\'e}ennes $a,b,\ldots,z$, les connecteurs binaires 
$\vee$ (OU) et $\wedge$ (ET), le connecteur unaire $\neg$ (NON) 
et les deux connecteurs 0-aires (c'est-{\`a}-dire les cons\-tantes bool{\'e}ennes) 
T (VRAI) et F (FAUX).
\smallskip

\textbf{III.A -}
Montrer que toute expression bool{\'e}enne est {\'e}quivalente {\`a} une expression 
utilisant uniquement $\wedge$ et $\neg$ comme connecteurs.
\smallskip

\textbf{III.B -}
Soit le connecteur ternaire $G(a,b,c)$ d{\'e}fini par :

\[
 G(a,b,c) = ( \neg(a) \wedge b \wedge c ) 
   \vee ( a \wedge (\neg(b))) 
   \vee ( \neg(b) \wedge \neg(c) )
\]

Montrer que toute expression bool{\'e}enne est {\'e}quivalente {\`a} une expression 
utilisant uniquement $G$ comme connecteur.
\smallskip

\textbf{III.C -}
Soit le connecteur binaire $-$ d{\'e}fini par 
$b - a = (\neg(a) \wedge b)$. 
Montrer que toute expression bool{\'e}enne est {\'e}quivalente {\`a} une expression 
utilisant uniquement $-$ et T comme connecteurs.
\smallskip

\textbf{III.D -}
Toute expression bool{\'e}enne est-elle {\'e}quivalente {\`a} une expression 
utilisant uniquement $-$ comme connecteur?
\smallskip

\end{document}
