From feeb71b1c50553cd53eb7ab9d6f488cb53153ae6 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 7 Nov 2016 15:23:35 +0100 Subject: Start writing course notes. --- notes-inf105.tex | 198 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 198 insertions(+) create mode 100644 notes-inf105.tex 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} -- cgit v1.2.3