path: root/notes-inf105.tex

%% 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{matrix}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}[subsection]
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newtheorem{defn}[comcnt]{Définition}
\newtheorem{prop}[comcnt]{Proposition}
\newtheorem{lem}[comcnt]{Lemme}
\newtheorem{thm}[comcnt]{Théorème}
\newtheorem{cor}[comcnt]{Corollaire}
\newtheorem{scho}[comcnt]{Scholie}
\newtheorem{algo}[comcnt]{Algorithme}
\renewcommand{\qedsymbol}{\smiley}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
%
\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}}
%
%
%
\begin{document}
\title{THL (Théorie des langages)\\Notes de cours \textcolor{red}{provisoires}}
\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


%
%
%

{\footnotesize
\tableofcontents
\par}

\bigbreak

\section{Alphabets, mots et langages}

\subsection{Introduction, alphabets, mots et longueur}

\thingy L'objet de ces notes, au confluent des mathématiques et de
l'informatique, est l'étude des \textbf{langages} : un langage étant
un ensemble de \textbf{mots}, eux-mêmes suites finies de
\textbf{lettres} choisies dans un \textbf{alphabet}, on va commencer
par définir ces différents termes avant de décrire plus précisément
l'objet de l'étude.

\thingy Le point de départ est donc ce que les mathématiciens
appelleront un \textbf{alphabet}, et qui correspond pour les
informaticiens à un \textbf{jeu de caractères}.  Il s'agit d'un
ensemble \emph{fini}, sans structure particulière, dont les éléments
s'appellent \textbf{lettres}, ou encore \textbf{caractères} dans une
terminologie plus informatique.

Les exemples mathématiques seront souvent donnés sur un alphabet tel
que l'alphabet à deux lettres $\{a,b\}$ ou à trois lettres
$\{a,b,c\}$.  On pourra aussi considérer l'alphabet $\{0,1\}$ appelé
\textbf{binaire} (puisque l'alphabet n'a pas de structure
particulière, cela ne fait guère de différence par rapport à n'importe
quel autre alphabet à deux lettres).  Dans un contexte informatique,
des jeux de caractères (=alphabets) souvent importants sont ASCII,
Latin-1 ou Unicode : en plus de former un ensemble, ces jeux de
caractère attribuent un numéro à chacun de leurs éléments (par
exemple, la lettre A majuscule porte le numéro 65 dans ces trois jeux
de caractères), mais cette structure supplémentaire ne nous
intéressera pas ici.  Dans tous les cas, il est important pour la
théorie que l'alphabet soit \emph{fini}.

L'alphabet sera généralement fixé une fois pour toutes dans la
discussion, et désigné par la lettre $\Sigma$ (sigma majuscule).

\thingy Un \textbf{mot} sur l'alphabet $\Sigma$ est une suite finie de
lettres (éléments de $\Sigma$) ; dans la terminologie informatique, on
parle plutôt de \textbf{chaîne de caractères}, qui est une suite finie
(=liste) de caractères.  Le mot est désigné en écrivant les lettres
les unes à la suite des autres : autrement dit, si $x_1,\ldots,x_n \in
\Sigma$ sont des lettres, le mot formé par la suite finie
$x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$.  À titre
d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma = \{a,b,c,d\}$,
et \texttt{foobar} est un mot (=chaîne de caractères) sur l'alphabet
ASCII.  (Dans un contexte informatique, il est fréquent d'utiliser une
sorte de guillemet pour délimiter les chaînes de caractères : on
écrira donc \texttt{\char`\"foobar\char`\"} pour parler du mot en
question.  Dans ces notes, nous utiliserons peu cette convention.)

L'ensemble des mots sur un alphabet $\Sigma$ est généralement
désigné $\Sigma^*$ (on verra que l'étoile fait partie d'un usage plus
général qui sera défini ci-dessous).  Par exemple, si $\Sigma =
\{0,1\}$, alors $\Sigma^*$ est l'ensemble (infini !) dont les éléments
sont toutes les suites finies binaires (=suites finies de $0$ et
de $1$).

\thingy Le nombre $n$ de lettres dans un mot $w \in \Sigma^*$ est
appelé la \textbf{longueur} du mot, et généralement notée $|w|$ ou
bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in \Sigma$, alors
la longueur $\ell(x_1\cdots x_n)$ du mot $x_1\cdots x_n$, vaut $n$.
Ceci coïncide bien avec la notion usuelle de longueur d'une chaîne de
caractères en informatique.  À titre d'exemple, sur l'alphabet
$\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$ (on écrira
$|abbcab|=6$ ou bien $\ell(abbcab)=6$).

\thingy Quel que soit l'alphabet, il existe un unique mot de
longueur $0$, c'est-à-dire un unique mot n'ayant aucune lettre, appelé
le \textbf{mot vide} (ou la \textbf{chaîne [de caractères] vide}).
Étant donné qu'il n'est pas commode de désigner un objet par une
absence de symbole, on introduit un symbole spécial, généralement
$\varepsilon$, pour désigner ce mot vide : on a donc
$|\varepsilon|=0$.  On souligne que le symbole $\varepsilon$
\underline{ne fait pas partie} de l'alphabet $\Sigma$, c'est un
symbole \emph{spécial} qui a été introduit pour désigner le mot vide.
(Lorsque les mots sont délimités par des guillemets, comme il est
usage pour les chaînes de caractères en informatique, le mot vide n'a
pas besoin d'un symbole spécial : il s'écrit juste
\texttt{\char`\"\char`\"} — sans aucun caractère entre les
guillemets.)

{\footnotesize Lorsque l'alphabet $\Sigma$ est \emph{vide},
  c'est-à-dire $\Sigma=\varnothing$, alors le mot vide est le seul mot
  qui existe : on a $\Sigma^*=\{\varepsilon\}$ dans ce cas.  C'est la
  seule situation où l'ensemble $\Sigma^*$ des mots est un ensemble
  fini.  Dans la suite, nous négligerons parfois ce cas particulier,
  qu'on pourra oublier : c'est-à-dire que nous ferons parfois
  l'hypothèse tacite que $\Sigma \neq \varnothing$.\par}

La notation $\Sigma^+$ est parfois utilisée pour désigner l'ensemble
des mots \emph{non vides} sur l'alphabet $\Sigma$ (par opposition à
$\Sigma^*$ qui désigne l'ensemble de tous les mots, y compris le mot
vide).

\thingy Les mots d'une seule lettre sont naturellement en
correspondance avec les lettres elles-mêmes : on identifiera souvent
tacitement, quoique un peu abusivement, une lettre $x\in\Sigma$ et le
mot de longueur $1$ formé de la seule lettre $x$.  (En informatique,
cette identification entre \emph{caractères} et \emph{chaînes de
  caractères de longueur $1$} est faite par certains langages de
programmation, mais pas par tous : \textit{caveat programmator}.)
Ceci permet d'écrire par exemple $\Sigma \subseteq \Sigma^*$ ou bien
$|x|=1 \liff x\in\Sigma$.

\thingy Si le cardinal de l'alphabet $\Sigma$ vaut $\#\Sigma = N$,
alors, pour chaque $n$, le nombre de mots de longueur exactement $n$
est égal à $N^n$ (combinatoire classique).  Le nombre de mots de
longueur $\leq n$ vaut donc $1 + N + \cdots + N^n =
\frac{N^{n+1}-1}{N-1}$ (somme d'une série géométrique).


\subsection{Concaténation de mots, préfixes, suffixes, facteurs, sous-mots}

\thingy Si $u := x_1\cdots x_m$ et $v := y_1\cdots y_n$ sont deux
mots, de longueurs respectives $m$ et $n$, sur un même
alphabet $\Sigma$, alors on définit un mot $uv := x_1\cdots x_m
y_1\cdots y_n$ de longueur $m+n$, dont les lettres sont obtenues en
mettant bout à bout celles de $u$ puis celles de $v$ (dans cet ordre),
et on l'appelle \textbf{concaténation} (ou, si cela ne prête pas à
confusion, simplement \textbf{produit}) des mots $u$ et $v$.  (Dans un
contexte informatique, on parle de concaténation de chaînes de
caractères.)

\thingy Parmi les propriétés de la concaténation, signalons les faits
suivants :
\begin{itemize}
\item le mot vide $\varepsilon$ est « \textbf{neutre} » pour la
  concaténation, ce qui signifie par définition : $\varepsilon w = w
  \varepsilon = w$ quel que soit le mot $w \in \Sigma^*$ ;
\item la concaténation est « \textbf{associative} », ce qui signifie
  par définition : $u(vw) = (uv)w$ quels que soient les mots $u,v,w
  \in \Sigma^*$.
\end{itemize}

On peut traduire de façon savante ces deux propriétés en une phrase :
l'ensemble $\Sigma^*$ est un \textbf{monoïde}, d'élément
neutre $\varepsilon$, pour la concaténation (cela signifie exactement
ce qui vient d'être dit).

\thingy On a par ailleurs $|uv| = |u| + |v|$ (la longueur de la
concaténation de deux mots est la somme des concaténations), et on
rappelle par ailleurs que $|\varepsilon| = 0$ ; on peut traduire cela
de manière savante : la longueur est un \textbf{morphisme de monoïdes}
entre le monoïde $\Sigma^*$ des mots (pour la concaténation) et le
monoïde $\mathbb{N}$ des entiers naturels (pour l'addition) (cela
signifie exactement ce qui vient d'être dit).

{\footnotesize\thingy \textbf{Complément :} Le monoïde $\Sigma^*$
  possède la propriété suivante par rapport à l'ensemble $\Sigma$ : si
  $M$ est un monoïde quelconque (c'est-à-dire un ensemble muni d'une
  opération binaire associative $\cdot$ et d'un élément $e$ neutre
  pour cette opération), et si $\psi\colon \Sigma\to M$ est une
  application quelconque, alors il existe un unique morphisme de
  monoïdes $\hat\psi\colon \Sigma^* \to M$ (c'est-à-dire une
  application préservant le neutre et l'opération binaire) tel que
  $\hat\psi(x) = \psi(x)$ si $x\in\Sigma$.  (Démonstration : on a
  nécessairement $\hat\psi(x_1\cdots x_n) = \psi(x_1)\cdots
  \psi(x_n)$, or ceci définit bien un morphisme comme annoncé.)  On
  dit qu'il s'agit là d'une propriété « universelle », et plus
  précisément que $\Sigma^*$ est le \textbf{monoïde libre} sur
  l'ensemble $\Sigma$.  Par exemple, le morphisme « longueur »
  $\ell\colon\Sigma^*\to\mathbb{N}$ est le $\ell = \hat\psi$ obtenu en
  appliquant cette propriété à la fonction $\psi(x) = 1$ pour
  tout $x\in\Sigma$.\par}

\thingy Lorsque $u,v,w \in \Sigma^*$ vérifient $w = uv$, autrement dit
lorsque le mot $w$ est la concaténation des deux mots $u$ et $v$, on
dira également :
\begin{itemize}
\item que $u$ est un \textbf{préfixe} de $w$, ou
\item que $v$ est un \textbf{suffixe} de $w$.
\end{itemize}

De façon équivalente, si $w = x_1\cdots x_n$ (où $x_1,\ldots,x_n \in
\Sigma$) est un mot de longueur $n$, et si $0\leq k\leq n$ est un
entier quelconque compris entre $0$ et $n$, on dira que $u :=
x_1\cdots x_k$ (c'est-à-dire, le mot formé des $k$ premières lettres
de $w$, dans le même ordre) est le \textbf{préfixe de longueur $k$}
de $w$, et que $v := x_{k+1}\cdots x_n$ (mot formé des $n-k$ dernières
lettres de $w$, dans le même ordre) est le \textbf{suffixe de
  longueur $n-k$} de $w$.  Il est clair qu'il s'agit bien là de
l'unique façon d'écrire $w = uv$ avec $|u|=k$ et $|v|=n-k$, ce qui
fait le lien avec la définition donnée au paragraphe précédent ;
parfois on dira que $v$ est le suffixe \textbf{correspondant} à $u$ ou
que $u$ est le préfixe correspondant à $v$ (dans le mot $w$).

Le mot vide est préfixe et suffixe de n'importe quel mot.  Le mot $w$
lui-même est aussi un préfixe et un suffixe de lui-même.  Entre les
deux, pour n'importe quelle longueur $k$ donnée, il existe un unique
préfixe et un unique suffixe de longueur $k$.  (Il peut tout à fait se
produire que le préfixe et le suffixe de longueur $k$ soient égaux
pour d'autres $k$ que $0$ et $|w|$, comme le montre l'exemple qui
suit.)

À titre d'exemple, le mot $abbcab$ sur l'alphabet $\Sigma=\{a,b,c,d\}$
a les sept préfixes suivants, rangés par ordre croissant de longueur :
$\varepsilon$ (le mot vide), $a$, $ab$, $abb$, $abbc$, $abbca$ et
$abbcab$ lui-même ; il a les sept suffixes suivants, rangés par ordre
croissant de longueur : $\varepsilon$ (le mot vide), $b$, $ab$, $cab$,
$bcab$, $bbcab$ et $abbcab$ lui-même.  Le suffixe correspondant au
préfixe $abb$ est $bcab$ puisque $abbcab = (abb)(bcab)$.

\thingy Comme généralisation à la fois de la notion de préfixe et de
celle de suffixe, on a la notion de facteur : si $u_0,v,u_1 \in
\Sigma^*$ sont trois mots quelconques sur un même alphabet $\Sigma$,
et si $w = u_0 v u_1$ est leur concaténation, on dira que $v$ est un
\textbf{facteur} de $w$.  Alors qu'un préfixe ou suffixe du mot $w$
est déterminé simplement par sa longueur, un facteur est déterminé par
sa longueur et l'emplacement à partir duquel il commence.

À titre d'exemple, les facteurs du mot $abbcab$ sont : $\varepsilon$
(le mot vide), $a$, $b$, $c$, $ab$, $bb$, $bc$, $ca$, $abb$, $bbc$,
$bca$, $cab$, $abbc$, $bbca$, $bcab$, $abbca$, $bbcab$ et $abbcab$
lui-même.

Dans un contexte informatique, ce que nous appelons ici « facteur »
est souvent appelé « sous-chaîne [de caractères] ».  Il ne faut
cependant pas confondre ce concept avec celui de sous-mot défini
ci-dessous.

\thingy Si $u_0,\ldots,u_r$ et $v_1,\ldots,v_r$ sont des mots sur un
même alphabet $\Sigma$, on dira que $v := v_1\cdots v_r$ est un
\textbf{sous-mot} du mot $w := u_0 v_1 u_1 v_2 \cdots u_{r-1} v_r
u_r$.  En plus clair, cela signifie que $v$ est obtenu en ne gardant
que certaines lettres du mot $w$ (celles des $v_i$), dans le même
ordre, mais en en effaçant d'autres (celles des $u_i$) ; à la
différence du concept de facteur, celui de sous-mot n'exige pas que
les lettres gardées soient consécutives.

À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$
(obtenu en gardant les lettres soulignées ici :
$\underline{a}bb\underline{c}a\underline{b}$ ; pour se rattacher à la
définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 =
a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
\varepsilon$).


%
%
%
\end{document}