\input mias
\TD 3

{\bf AF d\'eterministes et complets} (AFDC).
\parm
Soit $\autom A$ un AF sur un alphabet $Vt$ de terminaux (cf. TD : feuille 2) : on dit que 
$u\in Vt^*$ est reconnu par $\autom A$ ssi $u$ d\'efinit un chemin qui part
de l'entr\'ee de $\autom A$ et aboutit \`a l'une de ses sorties.
On d\'esigne par $\l L(\autom A)$ le langage constitu\'e par l'ensemble de ces mots
et on l'appelle le {\sl langage engendr\'e par $\autom A$}. 
\pars
Une analyse lexicale simule le parcours que d\'efinit un mot dans un AF 
\`a partir de l'entr\'ee de celui--ci.
La proc\'edure principale d'une analyse lexicale se pr\'esente donc sch\'ematiquement
de la fa\c con suivante :
\prog
\p begin 
 \a ...
 \p st := entree ;\comm{ entr\'ee de l'AF }
 \p ...
 \p while not eof do begin
  \a c := lire\_caractere( ) ;\comm{ lecture du caract\`ere suivant ...}
  \p ...                      \comm{... du mot \`a analyser }
  \p st := transition( st, c ) ;\comm{ passage de st \`a st$\action$c }
  \p if st in sorties then action( ) \comm{ on a reconnu un mot ...}
  \p        \comm{... on peut donc agir en cons\'equence }
  \p else 
  \p ... \comm{ continuer ou constater une <<erreur>>}
  \r end ; 
 \p ...
\r end .
\endprog
La fonction {\tt transition}, telle qu'elle est utilis\'ee ici,
suppose  que pour tout \'etat
$q$ de $\autom A$ et tout $x\in Vt$, $q\action x$ comporte exactement un \'el\'ement ;
un AF qui v\'erifie cette propri\'et\'e est dit {\sl d\'eterministe} (au plus un \'el\'ement) et
{\sl complet} (au moins un \'el\'ement) : en abr\'eg\'e on parlera d'un AFDC (sur $Vt$). Pour utiliser le sch\'ema
de programme ci--dessus, il est donc int\'eressant de savoir transformer
un AF $\autom A$ en un AFDC qui engendre le m\^eme langage que $\autom A$.
\par\vskip .5cm
{\bf AFDC associ\'e \`a un AF.}
\par
Soit $\autom A = (Q, q_0, \l F, \action)$ un AF sur l'alphabet $Vt$. 
\par
Alors, on construit les \'el\'ements de l'AFDC  $\autom B = (R, U_0, \l G, \actionb)$ de la fa\c con suivante :
\pars
{\parindent 1cm
\item{--} $R = \parties Q$ : les nouveaux \'etats sont des ensembles d'anciens \'etats,\par
\item{--} $U_0 = \{ q_0\}$ : la nouvelle entr\'ee est le singleton d\'efini 
par l'ancienne entr\'ee,\par
\item{--} $\l G$ : un nouvel \'etat est une sortie ssi il contient une ancienne 
sortie, c'est--\`a--dire : \par
\hfil $U\in \l G$ ssi $U\cap \l F \not = \vide$\parm
\item{--} $U\actionb x$ : pour tout $U\in R$ et tout $x\in Vt$, $U\actionb x\in R$ 
est la r\'eunion des ensembles $q\action x$ lorsque $q$ parcourt
 $U$, c'est--\`a--dire  : \par
\item{} {\sl pour tout $r\in Q$  : \parm
\hfil $r \in U\actionb x$ ssi il existe $q\in U$ tel que $r\in q\action x$}.
\par
}
\parm
L'AF $\autom B$ est d\'eterministe et complet par construction : l'objet de l'exercice 
est de comprendre cette construction et de v\'erifier que l'on a bien 
$\l L(\autom B)  = \l L(\autom A)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q a V\'erifier que la table de droite ci--dessous est bien celle de l'AFDC 
$\l L(\autom B)$ associ\'e
\`a l'AF $\l L(\autom A)$ d\'efini par celle de gauche.
\parm
\centerline{
$\boxit{1pt}{\vtop{
\offinterlineskip
\halign{\tv#&&\cc{$\displaystyle#$}&\tv#\cr\trait
&e/s&&q&&q\action a&&q\action b&\cr\trait
&\es&&S&&S, A&&B&\cr\trait
&\s&&A&&A&&B&\cr\trait
& &&B&&\vide&&A, B&\cr\trait
}}}$
\hfill
$\boxit{1pt}{\vtop{
\offinterlineskip
\halign{\tv#&&\cc{$\displaystyle#$}&\tv#\cr\trait
&e/s&&U&&U\actionb a&&U\actionb b&\cr\trait
&\es&&U_0 = \{S\}\hfill&&U_1&&U_2&\cr\trait
&\s&&U_1 = \{S, A\}\hfill&&U_1&&U_2&\cr\trait
& &&U_2 = \{B\}\hfill&&\vide&&U_3&\cr\trait
&\s&&U_3 = \{A,B\}\hfill&&U_4&&U_3&\cr\trait
&\s&&U_4 = \{A\}\hfill&&U_4&&U_2&\cr\trait
& &&\vide\hfill&&\vide&&\vide&\cr\trait
}}}$
}
\parm
\puce Il faut remarquer que, dans la table de $\autom B$, 
$\{S, B\}$ ni $\{S, A, B\}$ n'ont \'et\'e retenus : 
en fait, ces \'etats n'\'etant pas accessibles \`a partir 
de l'entr\'ee, ils ne jouent aucun r™le dans la reconnaissance d'un mot et peuvent
donc \^etre n\'eglig\'es sans dommage !
\puce L'\'etat vide $\vide$ est une impasse dont on ne peut jamais s'\'echapper : cet
\'etat correspond donc toujours \`a une <<erreur>> (c'est--\`a--dire qu'un
mot qui y conduit n'est pas reconnaissable par l'AF). 
\Q b
Pour chacun des deux mots $u = a^3 = aaa$ et $v = a^2b^4 = aabbbb$, mettre en correspondance
\pars
{\parindent 1cm
\item{--} tous les chemins dans $\autom A$ qu'ils d\'efinissent en partant de l'entr\'ee,\par
\item{--} idem, dans $\autom B$.\par
}
\pars
Ce que vous venez d'observer est--il vrai pour tous les mots ?
\parm
\line{
\vtop{\hsize = 5.9cm
\Q c 
Appliquer la construction \`a l'AF d\'efini par la table 
ci--contre
et refaire l'exp\'erience de la question pr\'ec\'edente, avec des mots de votre choix.
\Q d V\'erifier que, pour tout AF $\autom A$, l'AFDC associ\'e $\autom B$ est tel
que \pars
\hfil $\l L(\autom B)  = \l L(\autom A)$.\par
}
\hfill 
$\boxit{1pt}{\vtop{
\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
}}}$
}
\parm


\bye