<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">

\begin{Exo}[Construction par sous-ensembles]
ReprÃ©senter graphiquement l'AFND dont la table de la relation de transition des Ã©tats est donnÃ©e par :
$$
\begin{array}{|c|c|c|}
\hline
t &amp; a &amp; b \\
\hline
0 &amp; 0,1 &amp; 3 \\
\hline
1 &amp; - &amp; 2 \\
\hline
2 &amp; 2 &amp; 1 \\
\hline
3 &amp; - &amp; 0,1,2\\
\hline
\end{array}
$$
Les Ã©tats initiaux sont 0 et 1, le seul Ã©tat d'acceptation est 2. Le dÃ©terminiser en lui appliquant la \og construction par sous-ensembles \fg{} ; donner le graphe du rÃ©sultat obtenu.
\end{Exo}


\begin{Exo}[Automate-Quotient]
 On donne la table de transition des Ã©tats d'un AFD :
$$\begin{array}{|c|c|c|c|}
\hline
t &amp; a &amp; b &amp; c \\
\hline
r &amp; r&amp; v &amp; r \\
\hline
s &amp; s &amp; p &amp; s \\
\hline
u &amp; r &amp; v &amp; s \\
\hline
v &amp; r &amp; v &amp; s \\
\hline
\end{array}
$$
Soit $\mathcal{R}$ la plus petite relation d'Ã©quivalence sur $E$ (ensemble des Ã©tats) telle que $u \mathcal{R} v$, $p \mathcal{R} v$ et $s \mathcal{R}$.
\begin{enumerate}
\item VÃ©rifier qu'il s'agit d'une congruence d'automates et dessiner le graphe de l'automate-quotient.

\item Sachant que, dans l'automate d'origine, l'Ã©tat initial est $p$ et que le seul Ã©tat d'acceptation est $u$, dÃ©crire le langage reconnu par l'automate.
\end{enumerate}
\end{Exo}


\begin{Exo}[Construction d'automates de Moore]
On demande de dÃ©ssiner un automate de moore reconnaissant le langage :
\begin{enumerate}
\item dÃ©crit par l'expression rationnelle $(a|bb)^*bab^*$,
\item dÃ©fini par l'expression rationnelle $(a|b|c)^*(abc|cba)$,
\item dÃ©fini sur l'alphabet $\{a,b\}$ des mots non vides ne comportant pas plus de 2 lettres $b$ consÃ©cutives.
\end{enumerate}
\end{Exo}

\gsaut
\centerline{\x{Fin du Chapitre}}</pre></body></html>