logique/exercicesLogique.tex

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