\documentclass[a4paper]{article}


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

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

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

\begin{exercice}
  Montrez que tout langage sensible au contexte est r\'ecursif.
\end{exercice}

\begin{exercice}
  Montrez que le probl\`eme de d\'eterminer si une machine de Turing
  s'arr\^ete pour tout mot d'entr\'ee est ind\'ecidable.
\end{exercice}

\begin{exercice}
  Les deux probl\`emes suivants sont-ils d\'ecidables ou ind\'ecidables:
  \begin{enumerate}
  \item Étant donn\'es une machine de Turing $M$, un \'etat $q$ et une
    cha\^\i ne $w$, d\'eterminer si $M$ atteindra l'\'etat $q$ sachant qu'elle
    commence dans l' \'etat initial et que $w$ lui est fourni en
    entr\'ee.

  \item D\'eterminer si une machine de Turing donn\'ee $M$ s'arr\^ete apr\`es
    un nombre de mouvements constant $k$ sachant qu'elle commence dans
    l' \'etat initial et qu'une cha\^\i ne $w$ lui est fournie en entr\'ee.
  \end{enumerate}
\end{exercice}

\begin{exercice}

  On se donne les propri\'et\'es ci-dessous, et les \emph{propri\'et\'es
  des langages r\'ecursivement \'enum\'erables} associ\'ees.
  Utilisez le th\'eor\`eme de Rice pour les langages r\'ecursifs
  afin de d\'eterminer dans chaque cas si la propri\'et\'e engendre
  un probl\`eme $ L_P= \{ <M>\ |\ L(M)\in P \} $ d\'ecidable:

  \begin{enumerate}
  \item $L \neq \Sigma^*$

  \item $L \cap X \neq \emptyset$ avec $X$ un ensemble r\'ecursivement
    \'enum\'erable donn\'e

  \item $L$ contient au moins deux cha\^\i nes

  \item $L$ est infini

  \item $L$ est un langage hors-contexte

  \item $L=L^R$
  \end{enumerate}
\end{exercice}

\end{document}



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