\documentclass [a4paper,twoside] {article}

\usepackage {epic,eepic,amstex,amssymb,latexsym,epsfig,delarray,graphics,graphpap,alltt,graphicx}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem {exo} {Exercice \rm 3.\hspace {-.1cm}}
\newtheorem {exercice} {Exercice \rm 3.\hspace {-.1cm}}
\newtheorem {DEFx} {Définition \rm 3.\hspace {-.1cm}}
\newtheorem {THMx} {Théorême \rm 3.\hspace {-.1cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand {\meta} [1] {$\blacklozenge$-\texttt #1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

%\headsep=+50pt
%\oddsidemargin=10pt
%\textwidth=430pt
\topmargin=0pt
%\textheight=700pt
\oddsidemargin=+60pt
\evensidemargin=+60pt
%\footskip=+10pt

\title{\textbf {Eléments d' informatique théorique} \\
                  S\'erie 3 \\
         \textsl {}}
\date {}
\vspace {-100 mm}
\maketitle





\begin{exercice}\rm {\bf }

Construire un automate déterministe équivalent à l'automate:
  \begin{center}
    \input{elimineeps.eepic}
  \end{center}
\end{exercice}

\begin{DEFx}\rm{\bf Automate minimal}

Un AF déterministe $M=<Q,\Sigma,\delta,q_0,F>$ est
  \emph{minimal} si et seulement si pour tout AF déterministe
  $M'=<Q',\Sigma,\delta',q_0',F'>$ on a $L(M)=L(M')$ implique
  $|Q|\leq|Q'|$.]
\end{DEFx}

\begin{THMx}\rm {\bf Unicité d'automate minimal}

Soit $\cal M$ l'ensemble de tous les automates déterministes
  $M=<Q,\Sigma,\delta, q_0, F>$ qui reconnaîssent le même
  langage $L \subseteq \Sigma^*$. Soit
  $M'=<Q',\Sigma',\delta',q_0',F'>$ un automate déterministe
  minimal dans $\cal M$. Alors $M'$ est unique à isomorphisme
  près (renommage des états).
\end{THMx}

\begin{DEFx}\rm{\bf Algorithme de construction d'un automate minimal}


  \begin{enumerate}
  \item Eliminer les états inutiles.  Un état est inutile s'il n'y a
    pas de mot $m$ tel que $\delta^*(q_0,m)=q$.  L'état $q$ est aussi
    inutile s'il n'y a pas de mot $n$ tel que $\delta^*(q,n)\in F$.
  
  \item Trouver les classes d'équivalence d'états selon la relation
    $R$ suivante:
    \begin{quote}
      la relation $R(q,q')$ est vraie si et seulement si pour tout mot
      $m \in \Sigma^*$
      \begin{itemize}
      \item soit $\delta^*(q,m)\in F$ et $\delta^*(q',m)\in F$
      \item soit $\delta^*(q,m)\not\in F$ et $\delta^*(q',m)\not\in F$
      \end{itemize}
    \end{quote}
    Il suffit en fait de ne considérer que les mots $m$ avec
    $|m|\leq|Q|$.
    
  \item
    \begin{tabbing}
      Définir: \= $Q' = \{[q]\}$ (c.à.d les classes d'équivalence trouvées),\\
      \> $q_0' = [q_0]$, \\
      \> $\delta'([q],a) = [\delta(q,a)]$, \\
      \> $F'=\{[q]\mid q \in F\}$ et $\Sigma'=\Sigma$.
    \end{tabbing}
\end{enumerate}
\end{DEFx}

\begin{exercice}\rm {\bf }
  Minimaliser l'automate\,:
  \begin{center}
    \input{minimiser.eepic}
  \end{center}
\end{exercice}

\begin{exercice}\rm {\bf }

%  Démontrez formellement que la classe des langages (définis sur le
%  même alphabet) acceptés par les automates à états finis est fermée
%  par\,:
%  \begin{center}
%    1) l'union, \hspace{2cm} 2) l'intersection, \hspace{2cm} 3) la
%    complémentation.
  \end{center}
  Soient $L_1$ et $L_2$ les langages d\'ecid\'es par
  $M_1$ et $M_2$ respectivement. Construire les automates acceptant
  $L_1L_2$, $L_1\cup L_2$, $\bar L_1$, $\bar L_2$ et $L_1\cap L_2$.
  \begin{center}
    \input{combin.eepic}
  \end{center}
\end{exercice}

\end {document}


\begin{center}
\begin{figure}[htbp]
\centering \includegraphics[width=4cm]{Nom de la figure.ps}
\end{figure}
\end{center}

\begin{figure}[ht]
\begin{center}
\input{Nom de la figure.pstex_t}
\end{center}
\caption{Commentaire du dessin.}
\end{figure}
