%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{TD langages algébriques — Corrigé}
\else
\title{TD langages algébriques}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000


%
%
%

\exercice

Soit $\Sigma = \{a,b\}$.  Montrer que le langage $L := \{ww :
w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (par exemple,
$\varepsilon$, $aa$, $abab$, $abaaba$ ou encore $aabbaabb$) n'est pas
algébrique.  On pourra pour considérer son intersection avec le
langage $L_0$ dénoté par l'expression rationnelle $a{*}b{*}a{*}b{*}$
et appliquer le lemme de pompage.

\begin{corrige}
Supposons par l'absurde que $L$ soit algébrique : alors son
intersection avec le langage rationnel $L_0 = \{a^m b^n a^{m'} b^{n'} :
m,n,m',n' \in \mathbb{N}\}$ est encore algébrique.  Or $L \cap L_0 =
\{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$.  On va maintenant utiliser
le lemme de pompage pour arriver à une contradiction.

Appliquons le lemme de pompage pour les langages algébriques au
langage $L \cap L_0 = \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$
considéré : appelons $k$ l'entier dont le lemme de pompage garantit
l'existence.  Considérons le mot $t := a^k b^k a^k b^k$ : dans la
suite de cette démonstration, on appellera « bloc » de $t$ un des
quatre facteurs $a^k$, $b^k$, $a^k$ et $b^k$.  D'après la propriété de
$k$ garantie par le lemme de pompage, il doit exister une
factorisation $t = uvwxy$ pour laquelle on a (i) $|vx|\geq 1$,
(ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in L \cap L_0$ pour
tout $i\geq 0$.

Chacun de $v$ et de $x$ doit être contenu dans un seul bloc, i.e.,
doit être de la forme $a^\ell$ ou $b^\ell$, sinon sa répétition ($v^i$
ou $x^i$ pour $i\geq 2$, qui appartient à $L_0$ d'après (iii)) ferait
apparaître plus d'alternations entre $a$ et $b$ que le langage $L_0$
ne le permet.  Par ailleurs, la propriété (ii) assure que le facteur
$vwx$ ne peut rencontrer qu'un ou deux blocs de $t$ (pas plus).
Autrement dit, $v$ et $x$ sont contenus dans deux blocs de $t$ qui
sont identiques ou bien consécutifs\footnote{La formulation est
  choisie pour avoir un sens même si $v$ ou $x$ est le mot vide (ce
  qui est possible \textit{a priori}).}.

D'après la propriété (i), au moins l'un de $v$ et de $x$ n'est pas le
mot vide.  Si ce facteur non trivial est dans le premier bloc $a^k$,
l'autre ne peut pas être dans l'autre bloc $a^k$ d'après ce qui vient
d'être dit : donc $uv^iwx^iy$ est de la forme $a^{k'} b^n a^k b^k$
avec $k'>k$ si $i>1$, qui n'appartient pas à $L\cap L_0$, une
contradiction.  De même, le facteur non trivial est dans le premier
bloc $b^k$, l'autre ne peut pas être dans l'autre bloc $b^k$ : donc
$uv^iwx^iy$ est de la forme $a^m b^{k'} a^{m'} b^k$ avec $k'>k$ si
$i>1$, qui n'appartient pas à $L\cap L_0$, de nouveau une
contradiction.  Les deux autres cas sont analogues.
\end{corrige}


%
%
%
\end{document}