\documentclass [a4paper,twoside] {article}

\usepackage {epic,eepic,amstex,amssymb,latexsym,epsfig,delarray,graphics,graphpap,alltt,graphicx}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem {exercice} {Exercice \rm 4.\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 4 \\
         \textsl {}}
\date {}
\vspace {-100 mm}
\maketitle








\begin{exercice}{\bf }\rm
  Ecrire une grammaire régulière pour générer le langage
  $L=\{{0}({10})^n | n \geq 0\}$ et donner l'\textrm{AF}\ 
  correspondant.
\end{exercice}

\begin{exercice}{\bf }\rm
  Ecrire une grammaire régulière engendrant le langage défini par\,:
  \begin{center}
    \input{gramreg.eepic}
  \end{center}
\end{exercice}

\begin{exercice}{\bf }\rm
  Les grammaires suivantes ne sont pas régulières mais engendrent bien
  des langages réguliers. Donnez des grammaires régulières qui
  engendrent ces mêmes langages.
  \begin{enumerate}
  \item
    \begin{math}
      \begin{array}[t]{ccl}
        S & \longrightarrow & XY\\
        X & \longrightarrow &  aX \mid X  a \mid  a \\
        Y & \longrightarrow &  aY \mid Y  a \mid  a
      \end{array}
    \end{math}
  \item
    \begin{math}
      \begin{array}[t]{ccl}
        S & \longrightarrow & XYZ \\
        X & \longrightarrow &  a X \mid  b X \mid \epsilon \\
        Y & \longrightarrow &  a Y \mid  b Y \mid \epsilon \\
        Z & \longrightarrow &  a Z \mid \epsilon 
      \end{array}
    \end{math}
  \end{enumerate}
\end{exercice}
\newpage

\begin{exercice}{\bf Le berger, le loup, la chèvre et le chou.}\rm

\begin{quotation}
 Tout le monde connait le problème du berger, de la chèvre, du chou et du loup.
Le problème est le suivant:
\begin{quotation}\sl
 Un berger décide de faire traverser une rivière à une 
chèvre, un chou et un loup. Malheureusement en son absence, le loup mangerait la chèvre, de même, la chèvre mangerait le chou.
\end{quotation} 
\begin{itemize}
\item
Le problème à résoudre \emph{pour le berger} est de trouver un moyen de faire traverser tout ce petit monde et que tous les acteurs arrivent entier sur l'autre rive, avec comme restriction le fait que le berger ne peut prendre sur son embarcation qu' un seul autre ``passager'', sans quoi l' embarcation coulerait.
\item
Les problèmes à résoudre \emph{pour vous} sont les deux suivants:


\begin{enumerate}
\item
 Réaliser un automate à états finis qui résolve ce problème dans le sens suivant: 
\begin{quote}On considère l'alphabet $\{0,1,2,3\}$ où le 
symbole $0$ signifie que le berger traverse seul, le symbole $1$ qu'il traverse avec la chèvre, le symbole $2$ qu'il traverse avec le 
loup et $3$ qu'il traverse avec le chou. Un état rend compte de la position des différents acteurs sur une berge ou sur l'autre. 
L'état initial stipule que tous les acteurs sont sur la même rive. Un mot est une séquence de déplacements et un mot du langage doit 
conduire à un état où tous les acteurs sont sur la même rive (on peut faire plusieurs aller-retour).
\end{quote}
\item
Une fois l'automate réalisé, donner la grammaire régulière qui lui correspond.
\end{enumerate}
\end{itemize}
\end{quotation}
\end{exercice}

\begin{exercice}{\bf }\rm
  Donner une description explicative du langage engendr\'e par la
  grammaire suivant: 
  $S\rightarrow AB$, 
  $A\rightarrow a|aA|bAA|AAb|AbA$,
  $B\rightarrow b|bB|aBB|BaB|BBa$.
\end{exercice}

\begin{exercice}{\bf }\rm
  Minimiser l'automate suivant:
  \begin{figure}[ht]
    \begin{center}
      \input{maxistate.pstex_t}
    \end{center}
    \caption{Des \'etats inutiles?.}
  \end{figure}
\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}
