Start writing course notes.

1 files changed, 198 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
new file mode 100644
index 0000000..6d083d9
--- /dev/null
+++ b/notes-inf105.tex
@@ -0,0 +1,198 @@
+%% 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).
+
+
+%
+%
+%
+\end{document}