\documentclass [a4paper,twoside] {article}

\usepackage {epic,eepic,amsmath,amssymb,latexsym,epsfig,delarray,graphics,graphpap,alltt,graphicx}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem {exercice} {Exercice \rm 7.\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\'ements d'Informatique Th\'eorique} \\
                  S\'erie 7 \\
         \textsl {Machines de Turing}}
\date {}
\vspace {-100 mm}
\maketitle






\begin{quote}
{\sl Turing Machines probably epitomize the worst nightmare of programmers and computer scientists, but they are an invaluable tool used by mathematicians to define and establish complexity classes.\hfill{\em Adriano BARENCO}} 
\end{quote}

\begin{exercice}
  Construisez les machines de Turing acceptant les langages d\'efinis
  sur $\Sigma = \{\  a,\  b,\  c\}$\,.
  \renewcommand{\arraystretch}{1.5}
  \begin{eqnarray*}
  L_1&=&\{w\  cw \mid w \in \{\  a,\  b\}^+\}, \\
  L_2&=&\{w\  cw^R \mid w\in \{\  a,\  b\}^+\},\\
  L_3&=&\{\  a^n\  b^{n^2} \mid n\geq 1\},\\
  L_4&=&\{w\in \Sigma^* \mid \# \  a=\# \  b \mbox{ ou } \# \  a=\# \  c\}.
  \end{eqnarray*}
  (``$\#x$'' signifie le nombre de symboles $x$).\\
  Donnez la d\'efinition compl\`ete de la MT pour $L_1$ avec une
  repr\'esentation graphique de sa fonction de transition, puis donnez
  une d\'efinition simplifi\'ee des machines pour $L_2$, $L_3$ et $L_4$
  sous forme d'algorithme.
\end{exercice}

\begin{exercice}
  Construisez une MT à une bande acceptant le langage $L$ d\'efini sur
  $\sum = \{\  a,\  b\}$ suivant:
  $
  L=\{\  a^n\  b^n\mid n \geq 0 \} \cup \{\  a^n\  b^{2n} \mid n\geq 0\}.
  $
\end{exercice}

\begin{exercice}
  Construisez les machines de Turing calculant les fonctions
  suivantes\,.
  \[
  1)\ \ n^2,\quad\quad 2)\ \ n!,\quad\quad 3)\ \ \lfloor \log_2 n \rfloor.
  \]
\end{exercice}

\begin{exercice}
  Construisez des machines de Turing non d\'eterministes acceptant les
  langages:
  \begin{eqnarray*}
    L_1 &=& \{(a)^*(abb)^*(baa)^*\}, \\
    L_2 &=& \{ww^Ruu^R \mid w,u \in \{ a, b\}^* \}, \\
    L_3 &=& \{ a^n \mid n = p^2 + q^2 \;\mbox{et}\; p,q \ge 0 \}.
  \end{eqnarray*}
\end{exercice}


\begin{exercice}
\newcommand{\coefbin}[2]{{\left(\begin{array}{c}#1\\#2\end{array}\right)}}
  Construisez une machine de Turing calculant les coefficients bin\^omiaux:
  \[ 
  \coefbin{n}{k} = \left\{ \begin{array}{ll} \coefbin{n-1}{k-1} +
  \coefbin{n-1}{k} & \ \ {\rm si}\ 0 < k <  n \\ \vspace{2mm} 1 &
  \ \ {\rm sinon}
  \end{array}\right.
  \]
\end{exercice}

\begin{exercice}
  Montrez qu'un langage $L$ est accept\'e par une MT à une bande infinie
  des deux c\^ot\'es ssi $L$ est accept\'e par une MT à 1 seule bande.
\end{exercice}



\end{document}
% Local Variables: 
% mode: latex
% TeX-master: "main"
% End: 
