automates/exercices.tex

   1
   2
   3 \begin{Exo}[Construction par sous-ensembles]
   4 Représenter graphiquement l'AFND dont la table de la relation de transition des états est donnée par :
   5 $$
   6 \begin{array}{|c|c|c|}
   7 \hline
   8 t & a & b \\
   9 \hline
  10 0 & 0,1 & 3 \\
  11 \hline
  12 1 & - & 2 \\
  13 \hline
  14 2 & 2 & 1 \\
  15 \hline
  16 3 & - & 0,1,2\\
  17 \hline
  18 \end{array}
  19 $$
  20 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.
  21 \end{Exo}
  22
  23
  24 \begin{Exo}[Automate-Quotient]
  25  On donne la table de transition des états d'un AFD :
  26 $$\begin{array}{|c|c|c|c|}
  27 \hline
  28 t & a & b & c \\
  29 \hline
  30 r & r& v & r \\
  31 \hline
  32 s & s & p & s \\
  33 \hline
  34 u & r & v & s \\
  35 \hline
  36 v & r & v & s \\
  37 \hline
  38 \end{array}
  39 $$
  40 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}$.
  41 \begin{enumerate}
  42 \item Vérifier qu'il s'agit d'une congruence d'automates et dessiner le graphe de l'automate-quotient.
  43
  44 \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.
  45 \end{enumerate}
  46 \end{Exo}
  47
  48
  49 \begin{Exo}[Construction d'automates de Moore]
  50 On demande de déssiner un automate de moore reconnaissant le langage :
  51 \begin{enumerate}
  52 \item décrit par l'expression rationnelle $(a|bb)^*bab^*$,
  53 \item défini par l'expression rationnelle $(a|b|c)^*(abc|cba)$,
  54 \item défini sur l'alphabet $\{a,b\}$ des mots non vides ne comportant pas plus de 2 lettres $b$ consécutives.
  55 \end{enumerate}
  56 \end{Exo}
  57
  58 \gsaut
  59 \centerline{\x{Fin du Chapitre}}