\documentclass[twoside,a4paper]{article}


\usepackage{amsmath,amssymb,latexsym,epsfig,delarray,graphics,graphpap,alltt,graphicx,epic,eepic}


\newtheorem {exercice} {Exercice \rm 11.\hspace {-.1cm}}
\newcommand{\sy}[1]{\mbox{\crr #1}}
\newfont{\crr}{pcrr at 11pt}
\newcommand{\tuple}[1]{{\langle{#1}\rangle}} % <.>
\newcommand{\set}[1]{\{#1\}}
\newtheorem{DEFx}{D\'efinition}

\begin{document}

\title{\textbf {El\'ements d' informatique th\'eorique} \\
                  S\'erie 12 \\
         \textsl {}}
\date {}
\vspace {-100 mm}
\maketitle

\begin{exercice}
  Donnez les machines de Turing résolvant les problèmes ci-dessous et
  analysez les différentes complexités de leur calcul ! Envisagez
  d'éventuelles modifications afin d'améliorer ces dernières !
  \begin{enumerate}
  \item soustraire deux entiers en base 2,

  \item reconnaître le langage $L=\set{\sy a^n \sy b^n \sy c^n \mid n \geq 1}$,

  \item reconnaître le langage $L=\set{\sy a^n \sy b^{n^2} \mid n \geq 1}$,

  \item reconnaître le langage $L=\set{\sy a^n \sy b^n\mid n\geq 1} \cup
    \set{\sy a^n \sy b^{2n}\mid n \geq 1}$.
  \end{enumerate}
\end{exercice}

\begin{DEFx}{Crossing Sequence}
  Intuitivement une ``crossing sequence'' pour une position $z$ est la
  suite des états qui franchissent la limite entre la
  $z^{\mbox{\footnotesize ème}}$ et la $z+1^{\mbox{\footnotesize
      ème}}$ position à partir d'un certain état de départ $q_{t_0}$.
  On note cette ``crossing sequence'' par $CS(z)$. Pour l'illustration
  ci-dessous \(CS(z) = \{q_{t_{r}}, q_{t_{r+1}}, q_{t_{r+2}}, \ldots
  \}\).

  \begin{center}
  \input{crossing.eepic}
  \end{center}
\NOCLOSE
\end{DEFx}

\begin{exercice}
  Donnez une définition formelle de $CS(z)$ pour une machine de Turing
  à une bande.
\end{exercice}

\begin{exercice}
  Trouvez une machine de Turing à une bande acceptant $L= \{ w \sy c w^R
  \mid w \in \{0,1\}^* \}$, évaluez $CS(z)$ de cette machine ainsi que
  sa complexité en temps.
\end{exercice}

\end{document}



% Local Variables: 
% mode: latex
% TeX-master: "main"
% End: 
