\documentclass{amsart}

\textheight 250mm
\textwidth 180mm
\hoffset -32mm
\voffset -24mm

\newtheorem{theo}{Th\'eor\`eme}%[section]
\newtheorem{lemm}[theo]{Lemme}

\begin{document}
\noindent
\begin{tabular}{l c r}
\hline
Institut Galil\'ee - Universit\'e Paris 13 & \hskip 7cm \quad & Th\'eorie 
des langages \\
DEUG MIAS 2\`eme ann\'ee   & \hskip 8cm \quad & 24 mars 2000\\
\hline
\end{tabular}


\begin{center}{\Huge
Corrig\'e du devoir \`a la maison du 24 mars\\}
\end{center}

Deux questions d\'elicates de TD sont \'egalement trait\'ees en page 4. 

Un pseudo fascicule de d\'efinitions et de r\'esultats vous a 
 par ailleurs \'et\'e distribu\'e, il couvre surtout le programme de 
l'examen de juin.


\section{Mono\"{\i}des}

\subsection{} Un mono\"{\i}de est un ensemble muni d'une loi interne
 (partout d\'efinie, associative)
et d'un \'el\'ement neutre.

\subsection{} Un mono\"{\i}de libre est mono\"{\i}de avec une ``base''.
C'est-\`a-dire que ce mono\"{\i}de est {\em engendr\'e} par un ensemble
d'\'el\'ements {\em ind\'ependants} (=d\'epourvus de relations entre
eux). 
(``Base'' et ``libre''
sont donc \`a rapprocher des notions de base ou de libert\'e 
dans un espace vectoriel.)
On a ainsi une ``factorisation'' (=une d\'ecomposition) 
de chaque \'el\'ement du mono\"{\i}de libre en \'el\`ements de cette
``base''. On peut de plus alors d\'efinir la longueur d'un
\'el\'ement. Parfois, cette base est qualifi\'ee d'{\em alphabet},
les g\'en\'erateurs (= les \'el\'ements de la base) sont appel\'es 
{\em lettres} et les \'el\'ements du mono\"{\i}de libre
sont appel\'es {\em mots}, l'op\'eration associative
est appel\'ee {\em concat\'enation} et l'\'el\'ement neutre est appel\' {\em
mot vide}.
 

\subsection{} Exemple de mono\"{\i}de libre :
les entiers positifs ou nul avec l'addition comme op\'eration (elle
est bien associative et 0 est l'\'el\'ement neutre, la base est $\{1\}$).
 Exemple de mono\"{\i}de non libre : les entiers relatifs avec
l'addition comme op\'eration (la base est $\{-1,+1\}$ mais cette
base n'est pas ``libre'' car $(+1)+(-1)=0$).


Deux autres exemples seraient\\ 
mono\"{\i}de libre : l'ensemble $E_1$ des mots
contenants des $a$ ou des $b$, muni de la concat\'enation
comme loi interne et du mot vide comme \'el\'ement neutre.
La ``base'' de cet ensemble est $\{a,b\}$, $E$ est alors parfois 
not\'e  $\{a,b\}^*$ ;\\
mono\"{\i}de non libre : l'ensemble $E_2$ des mots
contenants des $a$ ou des $b$, muni de la concat\'enation
comme loi interne et du mot vide comme \'el\'ement neutre
et pour lequel on identifie les mots du type  $uabbv$ avec le mot $uv$. 
Cette fois-ci  $\{a,b\}$ n'est plus une base car on a la relation 
$abb=\epsilon$. 



\subsection{} 

Il y avait 143 mots \`a \'enum\'erer (travail fastidieux prenant 30
minutes avec les tr\`es n\'ecessaires v\'erifications).
Une pr\'esentation possible de tous ces mots peut se faire sous la
forme d'un arbre de possibilit\'es, pour une pr\'esentation 
plus ``lin\'eaire'',
on peut calculer les produits (jusqu'a 10) et faire l'union,
mais cela va peut-\^etre un peu plus vite
de s'apercevoir que $L^*$ repr\'esente les mots o\`u un $a$ est aussit\^ot suivi d'un $b$ et donc les mots
de longueur $<10$ sont {\small
\{$\epsilon$, 
b, 
ab, bb, 
bab, bbb, abb, 
abab, abbb, babb, bbab, bbbb, 
ababb, abbab, abbbb, babab, babbb, bbabb, bbbab, bbbbb,
ababab, ababbb, abbabb, abbbab, abbbbb, bababb, babbab, babbbb, bbabab, bbabbb,
bbbabb, bbbbab, bbbbbb, 
abababb, ababbab, ababbbb, abbabab, abbabbb, abbbabb, abbbbab, abbbbbb,
bababab, bababbb, babbabb, babbbab, babbbbb, bbababb, bbabbab, bbabbbb,
bbbabab, bbbabbb, bbbbabb, bbbbbab, bbbbbbb, 
abababab, abababbb, ababbabb, ababbbab, ababbbbb, abbababb, abbabbab, abbabbbb,
abbbabab, abbbabbb, abbbbabb, abbbbbab, abbbbbbb, babababb, bababbab, bababbbb,
babbabab, babbabbb, babbbabb, babbbbab, babbbbbb, bbababab, bbababbb, bbabbabb,
bbabbbab, bbabbbbb, bbbababb, bbbabbab, bbbabbbb, bbbbabab, bbbbabbb, bbbbbabb,
bbbbbbab, bbbbbbbb, 
ababababb, abababbab, abababbbb, ababbabab, ababbabbb, ababbbabb, ababbbbab,
ababbbbbb, abbababab, abbababbb, abbabbabb, abbabbbab, abbabbbbb, abbbababb,
abbbabbab, abbbabbbb, abbbbabab, abbbbabbb, abbbbbabb, abbbbbbab, abbbbbbbb,
babababab, babababbb, bababbabb, bababbbab, bababbbbb, babbababb, babbabbab,
babbabbbb, babbbabab, babbbabbb, babbbbabb, babbbbbab, babbbbbbb, bbabababb,
bbababbab, bbababbbb, bbabbabab, bbabbabbb, bbabbbabb, bbabbbbab, bbabbbbbb,
bbbababab, bbbababbb, bbbabbabb, bbbabbbab, bbbabbbbb, bbbbababb, bbbbabbab,
bbbbabbbb, bbbbbabab, bbbbbabbb, bbbbbbabb, bbbbbbbab, bbbbbbbbb\}}.

Certains auront peut-\^etre remarqu\'e que le nombre $a_n$ de mots de $L^*$
de longueur $n$ donne une suite $(a_n)$
qui v\'erifie la r\'ecurrence
$a_{n+2}=a_{n+1}+a_n$
(les premiers termes sont
$(1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...)$), il s'agit l\`a de la suite de
Fibonacci. La section 5 (Analyse et th\'eorie des langages) reviendra sur
ce type de consid\'erations.

\section{Grammaires}

\subsection{} 
$L_1$=\{les mots ne contenant pas deux $a$ cons\'ecutifs\} est engendr\'e par\\
 $$S\rightarrow \epsilon |a|B|BaBb|BaBba|,
\quad B\rightarrow bB|\epsilon$$
On engendre ainsi le mot vide, le mot $a$, 
les mots qui ne contiennent que des $b$, 
puis les mots qui contiennent des $a$ (n\'ecessairement suivi d'un $b$) et 
qui se terminent, soit par $b$, soit par $a$.

$L_2$=\{les mots contenant autant de $a$ que de $b$\} est engendr\'e par\\
$$S\rightarrow aSbS |bSaS| \epsilon$$
On a ainsi ``appari\'e'' les occurences de $a$ et $b$ pour assurer l'\'equilibre.

$L_3$ =\{les mots ne contenant que des $a$ (au moins un) puis que des $b$ (au moins un)\} est engendr\'e par\\
$$S\rightarrow aAbB, \quad A\rightarrow aA|\epsilon, \quad B
\rightarrow bB|\epsilon $$


$L_4$=\{les mots ne contenant que des $a$ puis que des $b$, avec
``nombre de $b$'' $>$ ``nombre de $a$'' $> 0$\}  est engendr\'e par\\
$$ S \rightarrow aSb |bS |\epsilon$$

$L_5$=\{les mots dont la parit\'e du nombre de $a$ \'egale celle du nombre de $b
$\} est engendr\'e par\\
$$S\rightarrow aT| bT |\epsilon, \quad T \rightarrow aS| bS $$

L'id\'ee de base consiste \'a partir du mot vide (dont la parit\'e
de nombre $a$ \'egale celle du nombre de $b$) et \'a observer
que si j'ajoute un $a$ ou un $b$, la parit\'e n'est plus \'egale,
et alors si j'ajoute un $a$ ou un $b$,  la parit\'e redevient \'egale.
On voit ainsi que tous les mots de longueur paire appartiennent \'a $L_5$
(et seulement eux!).


\subsection{} $L_1$ peut \^etre engendr\'e
 par la grammaire r\'eguli\`ere suivante :
 $$S\rightarrow bB|bA|aA|\epsilon, \quad
  B\rightarrow bB|\epsilon, \quad  A\rightarrow bB|bD, \quad   D\rightarrow aA|\epsilon$$

$L_3$ peut \^etre engendr\'e
par la grammaire r\'eguli\`ere suivante :
 $$S\rightarrow aA, \quad A\rightarrow aA|bB, \quad B
\rightarrow bB|\epsilon $$

La grammaire de $L_5$ est d\'ej\`a r\'eguli\`iere.

(Expressions rationnelles associ\'ees :
$L_1=b^*(ab^+)^*(\epsilon+a)$,  $L_3=a^+b^+$, $L_5=(aa+ab+ba+bb)^*$)

\subsection{} 
\`A l'aide du lemme de l'\'etoile (voir preuve, page 4), on va prouver que
$L_4=\{a^nb^{n+k}, n\geq 1, k>0\}$
 n'est pas r\'egulier. 
Supposons que $L_4$ est r\'egulier, regardons alors la d\'ecomposition
$u=u_1vu_2$ (pour $u$ un mot de $L_4$ ``assez long'') qui nous est donn\'ee par application du
lemme de l'\'etoile.
On devrait avoir $u_1v^i u_2 \in L_4$ pour tout $i\in {\bf N}$.
Or ceci est clairement impossible si $v$ ne contient que des $a$, 
ou si $v$ contient des $a$ et des $b$.

Donc les d\'ecompositions fournies ne peuvent donner 
que des $v$ qui ne contiennent que des $b$.

Or il existe dans $L_4$ des mots avec un pr\'efixe
contenant autant de $a$ cons\'ecutifs que l'on veut.

Ceci implique donc qu'avant m\^eme que l'on commence \`a lire des $b$
dans l'automate, on est d\'ej\`a pass\'e deux fois par le m\^eme 
\'etat. Ainsi, on a bien l'existence d'un facteur 
$v$ qui ne contient que des $a$,
ce qui contredit le point pr\'ecedent et donc ceci implique
que l'on ne pouvait appliquer le lemme de l'\'etoile,
et que le langage $L_4$ n'est donc pas r\'egulier.



\section{Expressions r\'eguli\`eres}

\subsection{} 
On commence par simplifier un peu l'expression~:
$(a^*b^*)$ contient $a$ et $b$, donc $(a^*b^*)^*= \{a, b\}^*$.
Ainsi  $$(a^*b^*)^*b+(ba)^*= \{a, b\}^*b+(ba)^*$$
et il s'agit donc de reconna\^{\i}tre tous les mots finissants par $b$
 et toutes les suites de $ba$.
La construction de l'automate ne pose aucun probl\`eme.

% \vskip 3cm

\subsection{} 
Enlevons la transition entre l'\'etat 4 et l'\'etat 1
et regardons l'automate $A'$ ainsi d\'efini.

 Par disjonction des cas, le langage $L'$ reconnu par cet automate est
 $$L'=a(ba)^*b + a(ba)^*ba +b(ab)^*a+b(ab)^*ab.$$

 Il est clair que $$\mathcal L(A)=(L'a)^*L'=((a(ba)^*(b+ba)+b(ab)^*(a+ab))a)^*(a(ba)^*(b+ba)+b(ab)^*(a+ab)).$$

Diverses autres formules \'equivalentes (\`a une factorisation pr\`es, etc.)
\'et\'e aussi acceptables.

\subsection{}%[20 min]
Impossible de donner une telle expression
car le langage n'est pas r\'egulier.

En effet, c'est une grammaire \'equivalente \`a
$$A\rightarrow aAbb|aab|ab^*A |\epsilon$$
qui est identique, \`a des changements de variables prets, \`a
$$A\rightarrow cAd|eA |f$$
et si on fait maintenant les substitutions  
($e\leftarrow \epsilon$ et $f \leftarrow \epsilon$),
on ne modifie pas la r\'egularit\'e du langage; 
or le langage engendr\'e par $$A\rightarrow cAd|\epsilon A |\epsilon $$
est $\{c^n d^n), n\in {\bf N}\}$, bien connu pour ne pas \^etre r\'egulier
(d\'emontr\'e en TD). CQFD~!

La transformation suivante a pour trace $aabbb$~:
$$A \rightarrow aBb \rightarrow Ab \rightarrow aC \rightarrow bC \rightarrow
A \rightarrow \epsilon$$


La grammaire est ambig\"ue car on peut trouver un autre arbre de 
d\'erivation, celui qui correspond \`a la transformation
$$A \rightarrow aC \rightarrow A a\rightarrow C \rightarrow bC \rightarrow 
bC \rightarrow bC \rightarrow A \rightarrow \epsilon$$



\section{Automates}

\subsection{} Il suffit d'enlever l'\'etat 0.

\subsection{} [dessin \`a faire] Application de l'algorithme vu en TD.

\subsection{} On ne peut pas faire mieux que l'automate donn\'e en 4.1.

\section{Analyse et th\'eorie des langages}


\subsection{} $$S \rightarrow 0S | 1S | \epsilon 
\Rightarrow S(z)=\frac{1}{1-2z}
$$

Dans le m\^eme genre, la s\'erie g\'en\'eratrice de 
$(ab,b)^*=\cup_{n \in \bf N} \{a,ab\}^n $
(cf. question 1.4) est $\sum (z+z^2)^n =\frac{1}{1-(z+z^2)}$.


\subsection{} 
La grammaire $S\rightarrow aSbS |\epsilon$ est non ambig\"ue et g\'en\`ere 
les mots de Dyck. La s\'erie g\'en\'eratrice est donn\'ee par

$$S\rightarrow aSbS |\epsilon \Rightarrow S(z)=z^2S(z)^2+1 \Rightarrow
L(z)=S(z)=\frac{1-\sqrt {1-4z^2}}{2z^2}$$

La division par $z^2$ n'est pas probl\'ematique en $z=0$, car on a en fait une
forme ind\'etermin\'ee $0/0$ qui s'av\`ere \^etre $=1$ (en utilisant des
d\'eveloppements limit\'es par exemple). En revanche,
la s\'erie a une singularit\'e (du type $\sqrt 0$) quand $1-4z^2=0$
donc quand $z=1/2$ qui est donc le rayon de convergence, 
on en d\'eduit (formule de Hadamard : rayon de convergence = 1/lim 
sup $a_n^{1/n}$) que les coefficients de la s\'erie croissent comme $2^n$.
C'est-\`a-dire qu'il y a environ $2^n$ mots de Dyck de longueur $n$
(pour $n$ pair, car pour $n$ impair, il y en a bien s\^ur 0).


\subsection{} D'apr\`es le th\'eor\`eme de
Chomsky-Sch\"utzenberger, $L_2$ n'est pas reconnaissable
car il engendr\'e par une grammaire non ambig\"ue et que
sa s\'erie g\'en\'eratrice est alg\'ebrique non rationnelle~:
$$S\rightarrow aSbS |bSaS| \epsilon \Rightarrow S(z)=2z^2S(z)^2+1 \Rightarrow
L(z)=S(z)=\frac{1-\sqrt {1-8z^2}}{4z^2}$$


\section{Automates et cha\^{\i}nes de Markov}

\subsection{} [dessin \`a faire]

\subsection{}  [dessin \`a faire]
%[20min +calcul formel] 


Comme les probabilit\'es d'arriv\'ees dans les diff\'erents \'etats
au bout de trois coups sont identiques, 
tout se joue apr\`es.

Soit $M_1$ la matrice donnant les transitions 
entre les 8 \'etats (apr\`es 3 coups)
pour $PPP$ final et $M_2$ la matrice pour $PFP$ final.
[dessin \`a faire]

Il faut alors utiliser un logiciel de calcul formel
pour calculer
$\sum M_1^n = (Id-M_1)^{-1}$ et $\sum M_2^n = (Id-M_2)^{-1}$.


La somme des \'el\'ements de la $i$-i\`eme ligne de l'inverse de $Id-M$
donne donc le nombre moyen de coups a faire avant d'atteindre 
l'\'etat correspondant.

On reviendra en TD sur cet exercice (dont la derni\`ere question est
totalement hors programme).

\section{Compilation}

Compiler, c'est transformer une ``phrase'' (un programme) d'un certain 
langage en
``quelque chose'' de compr\'ehensible par le microprocesseur.


$\bullet$ L'analyse lexicale (scanning) consiste \`a lire un par un les lettres ($=$ caract\`eres,
symboles...) afin de reconna\^{\i}tre des mots du langage, et donc 
de d\'ecouper la phrase initiale en suite de mots.

$\bullet$ L'analyse syntaxique (parsing) r\'epond \`a la question : cette suite de mots ainsi
obtenue est-elle ``grammaticalement'' correcte~? C'est-\`a-dire,
peut-on trouver une d\'erivation qui conduit \`a cette suite de mots ?

$\bullet$ L'analyse s\'emantique s'attache \`a d\'etecter des incoh\'erences
 de sens.

$\bullet$ L'optimisation consiste \`a simplifier l'arbre de d\'erivation ainsi obtenu.
 
$\bullet$ La g\'en\'eration de code consiste \`a associer 
des mots d'un nouveau langage (traduction en langage machine)
 aux  mots pr\'ec\'edemment reconnus.

$\bullet$ L'ex\'ecution est alors l' ``interpr\'etation'' par le micro-processeur
du code ainsi g\'en\'er\'e.


\section{TD1 Exercice 3. Question c)}

On rappelle qu'avec les notions de cette question, 
$bin(u)$ est le nombre d'op\'eration du mot $u$
et que $D(u)$ est le nombre de ``d\'ecoupage'' du mot $u$.


Nous allons faire une r\'ecurrence {\bf forte} sur $bin(u)$.

$\bullet$ [initialisation de la r\'ecurrence]\\
Quand $bin(u)=0$, on a donc utilis\'e ni la r\`egle 1 ni la r\`egle 2, 
on n'a donc aucune ambig\"uit\'e (l'arbre de d\'erivation de $u$
est en fait ``lin\'eaire'') et on a bien $$F(u)=Amb_G(u)=1.$$

$\bullet$ [h\'eridit\'e {\bf forte}]
Supposons que $F(u)=Amb_G(u)$ soit v\'erifi\'ee pour les $u$ tels que
$bin(u)\leq n$ ({\bf inf\'erieurs} ou \'egal, j'insiste), nous voulons montrer que $F(v)=Amb_G(v)$ pour
tous les $v$ tels que $bin(v)=n+1$.



Or un tel $v$ peut bien s\^ur s'\'ecrire sous la forme $v=u_1$ 
{\em op\'erateur} $u_2$, 
et donc $u_1$ et $u_2$ sont tels que $bin(u_1)\leq n$ et $bin(u_2)\leq n$.

Il y a tous les $D(u)$ comme d\'ecoupage possible, ceci r\'efl\`ete tout \`a fait les diff\'erents arbres de d\'erivations possibles~:
quand on regarde la racine, on a soit $S_1 \rightarrow S_2\times S_3$ soit 
$S_1 \rightarrow S_2+S_3$
avec $S_2$ qui va se d\'eriver en $u_1$ et $S_3$ qui va se d\'eriver en $u_2$.


Ainsi
$$Amb_G(u) = \sum_{(u_1, u_2)\in D(u)} Amb_G(u_1) Amb_G(u_2)
=\sum_{(u_1, u_2)\in D(u)} F(u_1) F(u_2)= F(u).$$


(La deuxi\`eme \'egalit\'e \'etant due \`a l'hypoth\`ese de 
r\'ecurrence forte.)


On a bien d\'emontr\'e $F=Amb_G$.



\section{TD2 Exercice 2}
\begin{lemm}[Lemme de l'\'etoile ou ``pumping lemma'']

Si $L$ est un langage r\'egulier
(c'est-\`a-dire $L=\mathcal L(G)$ pour une grammaire $G$ r\'eguli\`ere) alors~:\\
il existe un entier naturel $N>0$ tel que, pour tout $u\in L$ v\'erifiant $|u|\geq N$, 
on ait trois mots $u_1, v, u_2$ satisfaisant les conditions~:\\
1) $u=u_1vu_2$\\
2) $|v|\neq 0$\\
3) pour tout entier naturel $i$~: $u_1v^iu_2\in L$.

\end{lemm}

\begin{proof}
Pour un langage fini $L$ (i.e. qui contient un nombre fini de mots), 
le lemme de l'\'etoile est ``b\^etement'' v\'erifi\'e (car, en choississant
N:=1+``longueur du plus long mot de L'', on a aucun mot de longueur $\geq N$).


Pour un langage r\'egulier et infini $L$ (i.e. qui contient un nombre infini de mots), 
consid\'erons un automate $A$ tel que $L=\mathcal L (A)$ (il existe un tel
automate car {\bf Reg=Rec}, 
tout langage {\bf r\'eg}ulier est {\bf rec}onnu par 
un certain automate).
Notons $m$ le nombre d'\'etats de $A$.
Consid\'erons maintenant un mot $u\in L$ de longueur $>m$ (il existe for\c{c}\'ement un tel mot car le langage est infini), 
il existe donc un chemin dans $A$ qui part d'un \'etat initial, qui
passe obligatoirement (au moins) deux fois par le m\^eme \'etat $x$ (car $A$ n'a que $m$ \'etats), 
et qui termine dans un \'etat final.\\
Notons $u_1$ la trace du chemin entre l'\'etat initial et la premi\`ere fois 
que l'on est pass\'e par $x$.\\
Notons $u_2$ la trace du chemin entre la derni\`ere fois que l'on est pass\'e
par $x$ et l'\'etat final.\\
Notons $v$ la trace du chemin entre la premi\`ere et la derni\`ere fois que
l'on est pass\'e par $x$.\\
On a bien $u=u_1vu_2$ et $v\neq \epsilon$.
De plus, $\forall i, u_1v^iu_2$ est bien un mot de $L$
car il correspond \`a un chemin partant d'un \'etat initial et finissant dans un \'etat final.

%Dessin u_1 v (boucle) u_2

Il suffit donc de prendre $N=m+1$ et on a prouv\'e le lemme de l'\'etoile.

\end{proof}


\end{document}

