%% 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\label{non-square-words-is-algebraic}

Soit $\Sigma = \{a,b\}$.  On considère le langage $M$ des mots qui
\emph{ne s'écrivent pas} sous la forme $ww$ avec $w\in\Sigma^*$
(c'est-à-dire sous la forme d'un carré ; autrement dit, le langage $M$
est le \emph{complémentaire} du langage $Q$ des carrés considéré dans
l'exercice \ref{square-words-not-algebraic}) : par exemple, $M$
contient les mots $a$, $b$, $ab$, $aab$ et $aabb$ mais pas
$\varepsilon$, $aa$, $abab$ ni $abaaba$.

(0) Expliquer pourquoi tout mot sur $\Sigma$ de longueur impaire est
dans $M$, et pourquoi un mot $x_1\cdots x_{2n}$ de longueur paire $2n$
est dans $M$ si et seulement si il existe $i$ tel que $x_i \neq
x_{n+i}$.

On considère par ailleurs la grammaire hors contexte $G$
(d'axiome $S$)
\[
\begin{aligned}
S &\rightarrow A \;|\; B \;|\; AB \;|\; BA\\
A &\rightarrow a \;|\; aAa \;|\; aAb \;|\; bAa \;|\; bAb\\
B &\rightarrow b \;|\; aBa \;|\; aBb \;|\; bBa \;|\; bBb\\
\end{aligned}
\]

(1) Décrire le langage $L(G,A)$ des mots dérivant de $A$ dans la
grammaire $G$ (autrement dit, le langage engendré par la grammaire
identique à $G$ mais ayant pour axiome $A$).  Décrire de même
$L(G,B)$.

(2) Montrer que tout mot de longueur impaire est dans le
langage $L(G)$ engendré par $G$.

(3) Montrer que tout mot $t \in M$ de longueur paire est dans $L(G)$.
(Indication : si $t = x_1\cdots x_{2n}$ est de longueur paire $2n$ et
que $x_i \neq x_{n+i}$, on peut considérer la factorisation de $t$ en
$x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.)

(4) Montrer que tout mot de $L(G)$ de longueur paire est dans $M$.

(5) En déduire que $M$ est algébrique.

\begin{corrige}
(0) En remarquant que si $n = |w|$ alors $|ww| = 2n$, on constate que
  tout mot de la forme $ww$ est de longueur paire, et de plus, que
  pour un mot de longueur $2n$, être de la forme $ww$ signifie que son
  préfixe de longueur $n$ soit égal à son suffixe de longueur $n$ ;
  c'est-à-dire, si $t = x_1\cdots x_{2n}$, que $x_1\cdots x_n =
  x_{n+1}\cdots x_{2n}$, ce qui signifie exactement $x_i = x_{n+i}$
  pour tout $1\leq i\leq n$.

(1) La règle $A \rightarrow a \,|\, aAa \,|\, aAb \,|\, bAa \,|\, bAb$
  permet de faire à partir de $A$ une dérivation qui ajoute un nombre
  quelconque de fois une lettre ($a$ ou $b$) de chaque part de $A$, et
  finalement remplace ce $A$ par $a$.  On obtient donc ainsi
  exactement les mots de longueur impaire ayant un $a$ comme lettre
  centrale : $L(G,A) = \{w_1aw_2 : |w_1|=|w_2|\}$.  De même, $L(G,B) =
  \{w_1bw_2 : |w_1|=|w_2|\}$.

(2) Tout mot de longueur impaire est soit dans $L(G,A)$ soit dans
  $L(G,B)$ selon que sa lettre centrale est un $a$ ou un $b$.  Il est
  donc dans $L(G)$ en vertu des règles $S\rightarrow A$ et
  $S\rightarrow B$.

(3) Soit $t = x_1\cdots x_{2n}$ un mot de $M$ de longueur paire $2n$ :
  d'après (0), il existe $i$ tel que $x_i \neq x_{n+i}$.  Posons alors
  $u = x_1\cdots x_{2i-1}$ et $v = x_{2i}\cdots x_{2n}$.  Chacun de
  $u$ et de $v$ est de longueur impaire.  De plus, leurs lettres
  centrales sont respectivement $x_i$ et $x_{n+i}$, et elles sont
  différentes : l'une est donc un $a$ et l'autre un $b$ ; mettons sans
  perte de généralité que $x_i = a$ et $x_{n+i} = b$.  Alors $u \in
  L(G,A)$ d'après (1) et $v \in L(G,B)$ : le mot $t = uv$ s'obtient
  donc par la règle $S \rightarrow AB$ (suivie de dérivations de $u$ à
  partir de $A$ et de $v$ a partir de $B$) : ceci montre bien $t \in
  L(G)$.

(4) On a vu en (1) que tout mot dérivant de $A$ ou de $B$ est de
  longueur impaire.  Un mot $t$ de $L(G)$ de longueur paire dérive
  donc forcément de $AB$ ou de $BA$.  Sans perte de généralité,
  supposons qu'il dérive de $AB$, et on veut montrer qu'il appartient
  à $M$.  Appelons $u$ le facteur de $t$ qui dérive de $A$ et $v$ le
  facteur de $t$ qui dérive de $B$ : on sait alors (toujours
  d'après (1)) que $u$ s'écrit sous la forme $x_1\cdots x_{2i-1}$ où
  la lettre centrale $x_i$ vaut $a$, et que $v$ s'écrit sous la forme
  (quitte à continuer la numérotation des indices) $x_{2i}\cdots
  x_{2n}$ où la lettre centrale $x_{n+i}$ vaut $b$.  Alors $x_{n+i}
  \neq x_i$ donc le mot $t$ n'est pas dans $L$ d'après (0).

(5) On a $M = L(G)$ car d'après les questions précédentes, tout mot de
  longueur impaire est dans les deux et qu'un mot de longueur paire
  est dans l'un si et seulement si il est dans l'autre.  On a donc
  montré que $M$ est algébrique.
\end{corrige}


\exercice\label{square-words-not-algebraic}

Soit $\Sigma = \{a,b\}$.  Montrer que le langage $Q := \{ww :
w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (autrement dit,
des carrés ; par exemple, $\varepsilon$, $aa$, $abab$, $abaaba$ ou
encore $aabbaabb$ sont dans $Q$) 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 $Q$ 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 $Q \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 $Q \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 Q \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 à $Q\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 à $Q\cap L_0$, de nouveau une
contradiction.  Les deux autres cas sont analogues.
\end{corrige}

\textbf{Remarque :} Les exercices \ref{non-square-words-is-algebraic}
et \ref{square-words-not-algebraic} mis ensemble donnent un exemple
explicite d'un langage $M$ algébrique dont le complémentaire $Q$ n'est
pas algébrique.


%
%
%
\end{document}