\input mias
\TD 2


{\bf Grammaires}. Nous consid\'erons les grammaires r\'eguli\`eres $G = (Vn, Vt, P, S)$ 
dont les productions sont de la forme
$X\donne xY$ pour $x\in Vt$ et $X\donne \varepsilon$ (o\`u $\varepsilon$ est le mot vide).
\pars
{\bf Automates finis} (AF). Un automate fini 
$\autom A = (Q, q_0, \l F, \action)$ sur l'alphabet $Vt$ est la donn\'ee des 
\'el\'ements suivants :
\pars
{\parindent 1cm
\item{--} $Q$ : un ensemble fini (l'ensemble des \'etats),\par
\item{--} $q_0\in Q$ : entr\'ee de l'automate ou, \'etat initial,\par
\item{--} $\l F \subseteq Q$ : sorties de l'automate ou, \'etats terminaux,\par
\item{--} pour tout $q\in Q$ et tout $x\in Vt$ : $q\action x\subseteq Q$.\par
}
\pars
Un AF se pr\'esente g\'en\'eralement sous la forme d'une table (voir ci--dessous) mais, 
sa repr\'esentation sous la forme d'un graphe orient\'e sera encore plus suggestive :
\pars
{\parindent 1cm
\item{--} \`a chacun des \'etats correspond un n\oe ud du graphe,\par
\item{--} \`a chaque $r\in q\action x$ correspond une ar\^ete 
$q\buildrel\hbox{$x$}\over \longrightarrow r$,\par
\item{--} l'entr\'ee est d\'esign\'ee par une fl\^eche entrante,\par
\item{--} chaque sortie est d\'esign\'ee par une fl\^eche sortante.\par
}
\par
(Il est commode de pouvoir coller plusieurs \'etiquettes sur la m\^eme ar\^ete !).
\exo
\line{
\vtop{\hsize= 7cm
Le tableau ci--contre d\'efinit une correspondance entre les grammaires et les AF :
le but de cet exercice est d'illustrer cette correspondance par des exemples 
simples.
\parm
\Q a Construire l'AF correspondant \`a la grammaire dont les productions sont :
\pars
\hbox{
\vtop{\hsize = 1.45cm
$S\donne aS$\par
$A\donne aA$\par
$B\donne bA$\par
}\hfill
\vtop{\hsize = 1.45cm
$S\donne aA$\par
$A\donne bS$\par
$B\donne bB$\par
}\hfill
\vtop{\hsize = 1.45cm
$S\donne bB$\par
$A\donne \varepsilon$\par
}\hfill
\vtop{\hsize = 1.45cm
$S\donne \varepsilon$\par
}
}
}
\hfill 
$\boxit{1pt}{\vtop{
\offinterlineskip
\halign{\tv#&&\cc{$\displaystyle#$}&\tv#\cr\trait
&\hbox{Grammaire}&&\hbox{AF}&\cr\trait
&Vn&&Q&\cr\trait
&\hbox{Axiome}&&\hbox{Entr\'ee}&\cr\trait
&X\donne xY&&Y\in X\action x&\cr\trait
&X\donne\varepsilon&&X\in \l F&\cr\trait
}}}$
}
\parm
et dont $S$ est l'axiome. Dessiner le graphe repr\'esentant l'AF obtenu.
\parm
\Q b 
D\'efinir la grammaire correspondant \`a l'AF dont les \'el\'ements sont 
d\'ecrits dans la table ci--dessous.
\parb
\line{\hfill 
$\boxit{1pt}{\vbox{
\offinterlineskip
\halign{\tv#&&\cc{$\displaystyle#$}&\tv#\cr\trait
&e/s&&q&&q\action a&&q\action b&\cr\trait
&\es&&S&&A, D&&\vide&\cr\trait
& &&A&&S, B, D&&A, C&\cr\trait
&\s&&B&&A&&B, C&\cr\trait
& &&C&&B, C&&A&\cr\trait
&\s&&D&&\vide&&A&\cr\trait
}}}$
\hfill}
\pars
\Q c V\'erifier que, pour tout $u\in Vt^*$, chaque arbre de d\'erivation de $u$ dans $G$
d\'efinit un chemin dans $\autom A$ qui part de l'entr\'ee, aboutit \`a une sortie et
dont les \'etiquettes des ar\^etes successives forment le mot $u$, et r\'eciproquement.
\pars
On pourra s'appuyer sur les exemples pr\'ec\'edents.
\pars
{\bf Remarque.} Si on se reporte \`a  l'automate <<\`a ruban>> consid\'er\'e
dans le cours, on constate facilement que :
\pars
{\parindent 1cm
\item{--} $Y\in X\action x$ correspond \`a la transition $(x, X)\donne Y$,\par
\item{--} $X\in \l F$ correspond \`a la transition $(B, X)\donne S$ o\`u $S$ est l'axiome
de la grammaire et $B$ une cellule <<blanche>> du ruban.\par
\item{--} Le parcours d'un chemin qui va de l'entr\'ee jusqu'\`a une sortie de l'AF 
correspond \`a la lecture d'un mot par l'automate <<\`a ruban>>.\par
}
\exo
Montrer que si $L\subseteq Vt^*$ est un langage r\'egulier (c'est--\`a--dire si
$L = \l L(G)$ pour une grammaire comme ci--dessus) alors : 
\pars
{\sl il existe un 
entier naturel $N > 0$ tel que, pour tout $u\in L$ v\'erifiant $\longueur u\geq N$,
on ait trois mots $u_1$, $u_2$ et $v$ satisfaisant les conditions :\pars
\parindent 1cm
\item{1)} $u = u_1vu_2$\par
\item{2)} $\longueur v \not = 0$,\par
\item{3)} pour tout entier naturel $i$ : $u_1v^iu_2 \in L$.\par
}
\pars
{\bf Indication.} Une d\'erivation assez longue utilise n\'ecessairement au moins deux
fois le m\^eme non terminal (ou bien : un chemin assez long dans un AF passe n\'ecessairement 
deux fois au m\^eme endroit !).
\pars
{\bf Application.} Montrer que $L = \{a^m b^m\mid m\geq 0\}$ {\bf n'est pas} un langage
r\'egulier. (On raisonnera par l'absurde !)

\bye