% \setcounter{Exo}{0}
% \setcounter{Def}{0}
% \setcounter{Th}{0}
% \setcounter{Rem}{0}
% \setcounter{Notation}{0}
% \setcounter{Ex}{0}
\chapter{Exercices sur la logique}

\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 & a & b \\
\hline
0 & 0,1 & 3 \\
\hline
1 & - & 2 \\
\hline
2 & 2 & 1 \\
\hline
3 & - & 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 & a & b & c \\
\hline
r & r& v & r \\
\hline
s & s & p & s \\
\hline
u & r & v & s \\
\hline
v & r & v & 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}}