\documentclass[12pt,a4paper,twoside]{article}

\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{aafrench}
\input{c:/tex/aaa/oi/exs/exs} %inclue ifthen
%\usepackage{alltt}                          %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlg}    %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpic}  %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpicf} %DECOMMENTER CETTE LIGNE
%\newcommand{\FigMlPic}[3]{\mbox{}\\FIGURE\\} %COMMENTER CETTE LIGNE

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 \thispagestyle{empty}
  \sujet{Problème lié au génôme (ENS Cachan)}
   \texte
    Soit $X$ un alphabet. On dit qu'un mot $u\in X^*$
    \emph{se recombine} en $v\in X^*$, ce que l'on note $u\,\cc R\,v$, si
    $u=v$ sauf éventuellement un facteur  de $u$ à l'envers dans $v$.
   \question
    Formaliser la définition de $\cc R$.
   \question 
    Montrer que
    $\forall u,v\in X^*,\,\forall x\in X,\,u\,\cc R\,v
     \Leftrightarrow xu\,\cc R\,xv$.
   \question
    Donner un algorithme indiquant si $u\,\cc R\, v$. Complexité?
   \question\nf
    Si $L$ est un langage, on pose
    $L^{\cc R}=\{v\in X^*\,|\,\exists u\in L:u\,\cc R\,v\}$.\par\sl
    Peut-on dire que $L^{\cc R}$ est reconnaissable dés
    que $L$ est reconnaissable?.    
\paragraph*{Corrigé}\setcounter{questions}{0}\mbox{}
  \cquestion
   $u=u_1\dots u_n\,\cc R\,v=v_1\dots v_m$ ssi\\
   ou $u=v$, ou $n=m$ et il existe $1\leq i\leq j\leq n$ tels que
   $$\forall k=1,\dotsc,n,\,u_k=
    \begin{cases}
     v_{i+j-k}&\text{si }i\leq k\leq j\\
     v_k&\text{sinon.}
    \end{cases}$$
  \cquestion
   $\Leftarrow$ est évident. Réciproquement, si $xu\,\cc R\,xv$ et si
   le facteur de $xu$ à l'envers dans $xv$ est $xu_1\dots u_p$,
   $p\geq1$ (autres cas évidents), alors $v_p\dots v_1x=xu_1\dots u_p$;
   donc $v_p=x=u_p$ et $u=v$ sauf le facteur $u_1\dots u_{p-1}$
   à l'envers dans $v$.
  \cquestion
   Tant que la première (resp. la dernière) lettre de $u$ coïncide avec
   la première (resp. dernière) lettre de $v$, on supprime de $u$ et de $v$
   cette lettre; il reste alors à vérifier que $v$ est le miroir de $u$.
   Cet algorithme est linéaire.
  \cquestion
   Oui: si $\cc A=(Q,I,F,\Delta)$ est un automate reconnaissant $L$,
   alors
   $$L^{\cc R}=\sum_{p,q\in Q}I^{-1}p\widetilde{(p^{-1}q)}q^{-1}F$$
   où $\widetilde M$ désigne le langage miroir du langage $M$.
\end{parenthese}\end{document}
