%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input mias
\TD 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\baton{\mathop{\mkern 2mu 
\vrule height 1.5ex depth 0pt width .08em\mkern 2mu}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vskip 1cm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$\l A$ d\'esigne un alphabet quelconque.
\pars
{\bf Ensemble des mots sur $\l A$}. 
\par
On utilisera la d\'efinition suivante ({\sl construction des mots \`a partir du mot vide par adjonctions d'une lettre \`a droite}): 
\pars
{\parindent 1cm
\item{} {\sl l'ensemble $\l A^*$ des mots sur $\l A$}  est le plus petit ensemble tel que~: \par
\itemitem{(i)} $\varepsilon \in \l A^*$, o\`u $\varepsilon$ d\'esigne {\sl le mot vide}.\par
\itemitem{(ii)} pour tout $u\in \l A^*$ et tout $x\in \l A$, $ux\in \l A^*$.\par
}
 
%%%%%%%%
\exo
La concat\'enation peut se d\'efinir par r\'ecurrence de la fa\c con suivante :
\pars
{\parindent 2cm\par
\item{(i)} $u\concat \epsilon = u$ pour tout $u\in \l A^*$\par
\item{(ii)} $u\concat (vx) = (u\concat v)x$ pour tout $u\in \l A^*$, tout $v\in \l A^*$ et tout
$x\in \l A$\par
}\pars
On appliquera cette d\'efinition pour les questions suivantes.
\pars
\Q a Calculer $u\concat v$ pour $u = abab$ et $ v = aabb$.
\par
\Q b Montrer que l'on a $\epsilon \concat u = u$ et
$(u\concat v)\concat w = u\concat (v\concat w)$
quels que soient les mots $u$, $v$ et $w$.
\par
\Q c La {\sl longueur} $\longueur u$ de $u\in \l A^*$ peut se d\'efinir 
par r\'ecurrence de la fa\c con suivante : 
\pars
{\parindent 2cm\par
\item{(i)}$\longueur{\epsilon} = 0$.\par
\item{(ii)}$\longueur{ux} = \longueur u + 1$ pour tout $u\in \l A^*$ et tout
$x\in \l A$.
}\pars
V\'erifier que $\longueur{u\concat v} = \longueur u + \longueur v$.\par
\Q d D\'efinir le {\sl nombre d'occurrences} $\lg{u}{a}$ de $a\in \l A$ dans $u\in \l A^*$ et v\'erifier que $\lg{u\concat v}{a} = \lg{u}{a} + \lg{v}{a}$.\pars
Dans l'avenir, on notera simplement $uv$ pour $u\concat v$.\parb
{\bf Degr\'e d'ambigu\"\i t\'e d'un mot dans une grammaire}.\par
Soient $G = (Vt, Vn, R, S)$ une grammaire et $u\in Vt^*$.\par
Le degr\'e d'ambigu\"\i t\'e $Amb_G(u)$ de $u$ dans $G$ est le nombre d'arbres de d\'erivation de $u$ (deux \`a deux distincts). On notera en particulier que  :\pars
\centerline{$Amb_G(u)\not = 0$ si et seulement si $u\in \l L(G)$}
\exo
On consid\`ere la grammaire $G$ pour laquelle $Vt = \{\b a, \b c\}$, $Vn = \{S\}$ et $R$ est l'ensemble des productions~:
\pars
{\parindent 4cm
\initr
\item{} \r{S\donne \b a S}\par
\item{} \r{S\donne \b a S \b a}\par
\item{} \r{S\donne \b c}\par
}
\pars
\Q a Montrer que $\l L(G) = \{\b a^m \b c \b a^n \mid 0\leq n\leq m\}$.
\par
\Q b Calculer $A(m, n) = Amb_G(\b a^m \b c \b a^n)$ pour tous les couples d'entiers tels
que $0\leq n\leq m$. (Indication : l'observation de la production qui s'applique
\`a la racine d'un arbre de d\'erivation permet de faire un raisonnement par r\'ecurrence.)  

\exo
On consid\`ere la grammaire $G$ pour laquelle $Vt = \{+, \times , \baton\}$, $Vn = \{S, T\}$ et $R$ est l'ensemble des productions~:\pars
\line{\hfill
\initr
\vtop{\hsize 4cm 
\r{S\donne S\times S}\par
\r{S\donne S + S}\par
\r{S\donne T}
}
\kern 1cm
\vtop{\hsize 4cm 
\r{T\donne \baton T}\par
\r{T\donne \baton}\par
}
\hfill
}
\parb
\Q a Montrer que $u = \baton\baton \times\baton\baton\baton + \baton$ admet au moins deux arbres de d\'erivation diff\'erents dans $G$.
\par

\Q b Nous voulons  associer un \og calcul\fg\ \`a chaque arbre de d\'erivation $A$ d'un mot $u\in Vt^*$. Pour cela, on distingue chaque occurrence de $S$ et de $T$ qui s'y trouve par un indice qui lui est propre.\par
Montrer comment on peut alors attribuer une valeur enti\`ere \`a $u$ en appliquant en chaque n\oe ud de $A$ la relation appropri\'ee ci--dessous (les indices prennent la valeur qu'ils ont dans $A$)~:\parm
\line{\hfill
\initr
\vtop{\hsize 4cm
\r{S_i\donne S_j\times S_k}\par
\r{S_i\donne S_j + S_k}\par
\r{S_i \donne T_j}\par
\r{T_i\donne \baton T_j}\par
\r{T_i\donne \baton}\par
}
\kern 1cm
\vtop{\hsize 5cm
$\{val(S_i) = val(S_j) \times val(S_k)\}$\par
$\{val(S_i) = val(S_j) + val(S_k)\}$\par
$\{val(S_i) = val(T_j)\}$\par
$\{val(T_i) = 1 + val(T_j)\}$\par
$\{val(T_i) = 1\}$\par
}
\hfill
}
\parm
Calculer la valeur ainsi attribu\'ee \`a 
$u = \baton\baton \times\baton\baton\baton + \baton$ par deux arbres 
de d\'erivation distincts.
\par
\dQ{*}{c} Soit $bin(u)$ le nombre d'occurrences de $\times$ et $+$ dans $u$ et soit $D(u)$ l'ensemble des couples de mots d\'efini par~:\pars
\hfil $(u_1, u_2)\in D(u)$ ssi ``$u = u_1\times u_2$ ou $u = u_1 + u_2$'' \pars
On d\'efinit alors la fonction $F$ \`a valeur enti\`ere. Pour tout $u\in Vt^*$, on a~:\pars
{\parindent 2cm\par
Si $u = \varepsilon$,
}
	{\parindent 3cm\par
	Alors $F(u) = 0$\par
	Sinon si $bin(u) = 0$\par
	}
		{\parindent 4cm
		alors $F(u) = 1$\par
		sinon $F(u) = \somme{(u_1, u_2)\in D(u)}{F(u_1)F(u_2)}$
		}
\parm
Par exemple, on a~: \pars
\hfil $D(\baton\baton\times \baton + \baton) = 
\{(\baton\baton, \baton + \baton) , (\baton\baton\times \baton , \baton) \}$
et
$D(\times \baton\baton + \baton) = 
\{(\varepsilon, \baton\baton + \baton), (\times \baton\baton , \baton)\}$.
\pars
Montrer que $F(u) = Amb_G(u)$ pour tout $u\in Vt^*$.
\bye