%% 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

Considérons le fragment simplifié suivant de la grammaire d'un langage
de programmation hypothétique :
\[
\begin{aligned}
\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\ \mathtt{else}\ \mathit{Instruction}\\
|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
\end{aligned}
\]
(Ici, les « lettres » ou tokens ont été écrits comme des mots, par
exemple $\mathtt{foo}$ est une « lettre » : les terminaux sont écrits
en police à espacement fixe tandis que les nonterminaux sont en
italique et commencent par une majuscule.  On prendra
$\mathit{Instruction}$ pour axiome.)

(1) Donner l'arbre d'analyse de :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$ ;
expliquer brièvement pourquoi il n'y en a qu'un.

(2) Donner deux arbres d'analyse distincts de :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.
Que peut-on dire de la grammaire présentée ?

(3) En supposant que, dans ce langage,
$\mathtt{begin}\penalty0\ I\penalty0\ \penalty0\mathtt{end}$ (où $I$
est une instruction) a le même effet que $I$ seul, comment un
programmeur peut-il réécrire l'instruction considérée en (2) pour
obtenir un comportant équivalent à l'une ou l'autre des deux
interprétations ?

(4) Modifier légèrement la grammaire proposée de manière à obtenir une
grammaire faiblement équivalente dans laquelle seul l'un des arbres
d'analyse obtenus en (2) est possible (i.e., une grammaire qui force
cette interprétation-là par défaut) ; on pourra être amené à
introduire des nouveaux nonterminaux pour des variantes de
$\mathit{Instruction}$ et $\mathit{Conditional}$ qui interdisent
récursivement les conditionnelles sans $\mathtt{else}$.

\begin{corrige}
(1) L'arbre d'analyse de
  $\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$
  est le suivant (en notant $I$, $C$ et $E$ pour
  $\mathit{Instruction}$, $\mathit{Condition}$ et
  $\mathit{Expression}$ respectivement) :
\begin{center}
\tikzstyle{automaton}=[scale=0.4]
%%% begin ex2p1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
  \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$};
  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
  \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$};
  \node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
  \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
  \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
  \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
  \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
  \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
  \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
  \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
  \node (qux) at (387bp,162bp) [draw,draw=none] {$\mathtt{qux}$};
  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
  \node (C0) at (207bp,306bp) [draw,draw=none] {$C$};
  \node (E1) at (135bp,90bp) [draw,draw=none] {$E$};
  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
  \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp)  .. (foo);
  \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp)  .. (then0);
  \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp)  .. (C0);
  \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp)  .. (else0);
  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (else1);
  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (I2);
  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (E1);
  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (then1);
  \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp)  .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp)  .. (I4);
  \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp)  .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp)  .. (if1);
  \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp)  .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp)  .. (if0);
  \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp)  .. (trippy);
  \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp)  .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp)  .. (I3);
  \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp)  .. (I1);
  \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp)  .. (qux);
  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
  \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp)  .. (bar);
  \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp)  .. (E0);
%
\end{tikzpicture}

%%% end ex2p1 %%%
\end{center}

Il est le seul possible car une fois acquis que les deux $\mathtt{if}$
comportent chacun un $\mathtt{else}$, il se construit ensuite en
descendant de façon unique (l'instruction est forcément une condition,
qui s'analyse en $\mathtt{if}\ E\ \mathtt{then}\ I\ \mathtt{else}\ I$
de façon unique, et chacun des morceaux s'analyse de nouveau de façon
unique).

\vskip .5explus.1fil

(2) Un arbre d'analyse possible consiste à associer le
$\mathtt{else}\penalty0\ \mathtt{bar}$ avec
$\mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}$ :
\begin{center}
\tikzstyle{automaton}=[scale=0.4]
%%% begin ex2p1a %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
  \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$};
  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
  \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$};
  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
  \node (I0) at (135bp,378bp) [draw,draw=none] {$I$};
  \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
  \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
  \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
  \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
  \node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
  \node (C0) at (135bp,306bp) [draw,draw=none] {$C$};
  \node (E1) at (135bp,90bp) [draw,draw=none] {$E$};
  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
  \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp)  .. (foo);
  \draw [] (C0) ..controls (149.48bp,276.85bp) and (156.64bp,262.92bp)  .. (then0);
  \draw [] (I0) ..controls (135bp,348.85bp) and (135bp,334.92bp)  .. (C0);
  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (then1);
  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (else1);
  \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp)  .. (bar);
  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (E1);
  \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp)  .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp)  .. (if1);
  \draw [] (C0) ..controls (91.844bp,277.03bp) and (70.277bp,263.05bp)  .. (if0);
  \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp)  .. (trippy);
  \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp)  .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp)  .. (I3);
  \draw [] (C0) ..controls (178.16bp,277.03bp) and (199.72bp,263.05bp)  .. (I1);
  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (I2);
  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
  \draw [] (C0) ..controls (120.52bp,276.85bp) and (113.36bp,262.92bp)  .. (E0);
%
\end{tikzpicture}

%%% end ex2p1a %%%
\end{center}
un autre consiste à associer le $\mathtt{else}\penalty0\ \mathtt{bar}$
avec
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ ...$ :
\begin{center}
\tikzstyle{automaton}=[scale=0.4]
%%% begin ex2p1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (bar) at (387bp,162bp) [draw,draw=none] {$\mathtt{bar}$};
  \node (then1) at (279bp,90bp) [draw,draw=none] {$\mathtt{then}$};
  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
  \node (if1) at (135bp,90bp) [draw,draw=none] {$\mathtt{if}$};
  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
  \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
  \node (I2) at (351bp,90bp) [draw,draw=none] {$I$};
  \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
  \node (trippy) at (207bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
  \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
  \node (foo) at (351bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
  \node (C0) at (207bp,306bp) [draw,draw=none] {$C$};
  \node (E1) at (207bp,90bp) [draw,draw=none] {$E$};
  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
  \draw [] (I2) ..controls (351bp,60.846bp) and (351bp,46.917bp)  .. (foo);
  \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp)  .. (then0);
  \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp)  .. (C0);
  \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp)  .. (else0);
  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (I2);
  \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp)  .. (bar);
  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (E1);
  \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp)  .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp)  .. (I4);
  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (if1);
  \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp)  .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp)  .. (if0);
  \draw [] (E1) ..controls (207bp,60.846bp) and (207bp,46.917bp)  .. (trippy);
  \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp)  .. (I1);
  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (then1);
  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
  \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp)  .. (E0);
%
\end{tikzpicture}

%%% end ex2p1b %%%
\end{center}
La grammaire présentée est donc ambiguë.

\vskip .5explus.1fil

(3) Pour forcer la première interprétation (le
$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
$\mathtt{if}\penalty0\ \mathtt{trippy}$), on peut écrire :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{end}$.

Pour forcer la seconde interprétation (le
$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
$\mathtt{if}\penalty0\ \mathtt{happy}$), on peut écrire :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{end}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.

\vskip .5explus.1fil

(4) Pour forcer la première interprétation (le $\mathtt{else}$ se
rapporte au $\mathtt{if}$ le plus proche possible), on peut modifier
la grammaire comme suit :
\[
\begin{aligned}
\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
\mathit{InstrNoSC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{CondNoSC}\\
|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{Instruction}\\
|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
\mathit{CondNoSC} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{InstrNoSC}\\
\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
\end{aligned}
\]
L'idée est d'obliger une instruction conditionnelle qui apparaîtrait
après le $\mathtt{then}$ d'une conditionnelle complète à être
elle-même complète (elle ne peut pas être courte, car alors le
$\mathtt{else}$ devrait se rattacher à elle), et ce, récursivement.
On peut montrer que la grammaire ci-dessus est inambiguë et faiblement
équivalente à celle de départ.

On peut aussi fabriquer une grammaire inambiguë, faiblement
équivalente à celle de départ, qui force l'autre interprétation (le
$\mathtt{else}$ se rapporte au $\mathtt{if}$ le plus lointain
possible), mais c'est nettement plus complexe (l'idée générale pour
apparier un $\mathtt{else}$ avec un $\mathtt{if}...\mathtt{else}$ dans
cette logique est de demander que \emph{soit} le $\mathtt{else}$ n'est
suivi d'aucun autre $\mathtt{else}$, \emph{soit} toute instruction
conditionnelle entre le $\mathtt{then}$ et le $\mathtt{else}$ est
elle-même complète).  Contrairement à la grammaire précédente, cette
grammaire, bien qu'inambiguë, est probablement impossible à analyser
avec un analyseur LR (ou même, déterministe).
\end{corrige}


%
%
%

\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 $2n$
  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$ est dans $M$ 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
cela 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}