1 files changed, 633 insertions, 0 deletions
diff --git a/slides1.tex b/slides1.tex
new file mode 100644
index 0000000..b7c9120
--- /dev/null
+++ b/slides1.tex
@@ -0,0 +1,633 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[mathserif,a4paper]{beamer}
+%\documentclass[a4paper]{article}
+%\usepackage[envcountsect,noxcolor]{beamerarticle}
+%\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\DeclareUnicodeCharacter{00A0}{~}
+% Beamer theme:
+\usetheme{Goettingen}
+%\usecolortheme{albatross}
+%\usecolortheme{lily}
+%\setbeamercovered{transparent}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+%
+\usepackage{graphicx}
+\usepackage{tikz}
+\usetikzlibrary{matrix,arrows,snakes,calc}
+%
+\newcommand{\itempoint}{\strut\hbox{\color{beamerstructure}\donotcoloroutermaths$\blacktriangleright$}\nobreak\hskip.5em plus.5em\relax}
+\renewcommand{\thefootnote}{\textdagger}
+\newcommand{\ord}{\mathop\mathrm{ord}\nolimits}
+%
+%
+%
+\title{Mots, languages et langages rationnels}
+\subtitle{Théorie des langages (INF105)}
+\author[David Madore]{David A. Madore\\
+{\footnotesize Télécom ParisTech}\\
+\texttt{david.madore@enst.fr}}
+\date{17 octobre 2018}
+\mode<presentation>{%
+\beamertemplatenavigationsymbolsempty
+\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize\hyperlinkslideprev{$\leftarrow$}\insertframenumber/\inserttotalframenumber\hyperlinkslidenext{$\rightarrow$}}}}
+}
+\setbeamercolor{myhighlight}{fg=black,bg=white!90!green}
+\begin{document}
+\mode<article>{\maketitle}
+%
+\setlength\abovedisplayskip{2pt plus 2pt minus 2pt}
+\setlength\belowdisplayskip{2pt plus 2pt minus 2pt}
+%
+\frame{\titlepage}
+%
+\section*{Plan}
+\begin{frame}
+\frametitle{Plan}
+\tableofcontents
+\end{frame}
+%
+\section{Introduction}
+\begin{frame}
+\frametitle{Qu'est-ce que la théorie des langages ?}
+
+\itempoint Discipline à l'interface entre \textbf{mathématiques}
+discrètes et \textbf{informatique}.
+
+\bigskip
+
+\itempoint Trouve ses origines dans une étude formelle de la
+linguistique (Chomsky) et de la calculabilité (Turing).
+
+\bigskip
+
+\itempoint Cherche à développer des outils algorithmiques et concepts
+abstraits pour l'étude des \textbf{chaînes de caractères}
+(=~\textbf{mots}) et fichiers texte, p.ex. :
+\begin{itemize}
+\item recherche de motifs / remplacement,
+\item différences, substitutions,
+\item analyse syntaxique (p.ex. avant compilation).
+\end{itemize}
+
+\bigskip
+
+\itempoint Ce cours se concentrera sur trois aspects :
+\begin{itemize}
+\item langages et expressions rationnels, automates finis,
+\item grammaires hors contexte et arbres d'analyse,
+\item introduction à la calculabilité.
+\end{itemize}
+
+\end{frame}
+%
+\section{Alphabets, mots, longueur, concaténation}
+\begin{frame}
+\frametitle{Alphabet, lettres, mots, langages}
+
+Quatre concepts basiques :
+
+\medskip
+
+\itempoint L'\textbf{alphabet} (= jeu de caractères) est un ensemble
+\emph{fini}, généralement noté $\Sigma$, sans structure particulière.
+
+\smallskip
+
+{\footnotesize
+
+Souvent fixé pour toute la discussion, p.ex., $\Sigma = \{a,b,c\}$.
+
+\par}
+
+\medskip
+
+\itempoint Les éléments de $\Sigma$ s'appellent \textbf{lettres} ou
+\textbf{caractères}.
+
+\medskip
+
+\itempoint Un \textbf{mot} est une suite \emph{finie} de lettres.
+
+(L'ensemble des mots possibles se note $\Sigma^*$.)
+
+\medskip
+
+\itempoint Un \textbf{langage} est un ensemble (quelconque) de mots.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Alphabet et lettres}
+
+On considère un ensemble $\Sigma$ \emph{fini}, l'\textbf{alphabet},
+dont les éléments s'appellent \textbf{lettres} ou \textbf{caractères}
+(ou \textbf{symboles}).
+
+\bigskip
+
+P.ex., $\Sigma = \{0,1\}$ (alphabet \textbf{binaire}).
+
+\bigskip
+
+En informatique, on parle de \textbf{jeu de caractères}, p.ex., ASCII
+ou Unicode.
+
+\bigskip
+
+Pour les exemples, on utilisera souvent quelque chose comme $\Sigma =
+\{a,b\}$ ou $\{a,b,c\}$.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Mots}
+
+{\footnotesize(Rappel : $\Sigma$ est un ensemble \emph{fini}.)\par}
+
+\medskip
+
+\itempoint Un \textbf{mot} sur $\Sigma$ est une suite finie de lettres
+(= éléments de $\Sigma$).
+
+\smallskip
+
+En informatique, on parle de \textbf{chaîne de caractères}.
+
+\medskip
+
+\itempoint On notera sans séparateur : $x_1\cdots x_n$ le mot de $n$
+lettres (= longueur $n$) formé par $x_1,\ldots,x_n$.
+
+\medskip
+
+\itempoint \textbf{Longueur} d'un mot : $|x_1\cdots x_n| = n$.  Aussi
+notée $\ell(x_1\cdots x_n)$.
+
+\medskip
+
+\itempoint Il existe un unique mot de longueur $0$ : le \textbf{mot
+  vide}, généralement noté $\varepsilon$ (en informatique,
+\texttt{\char`\"\char`\"}).
+
+\smallskip
+
+{\footnotesize Le symbole $\varepsilon$ \alert{ne fait pas} partie de
+  l'alphabet !  C'est un symbole spécial.\par}
+
+\medskip
+
+\itempoint L'ensemble de tous les mots sur $\Sigma$ sera noté
+$\Sigma^*$.
+
+\smallskip
+
+{\footnotesize L'ensemble $\Sigma^*$ est toujours infini (sauf
+  si $\Sigma = \varnothing$).\par}
+
+\smallskip
+
+{\footnotesize P.ex. $\{a\}^* = \{\varnothing, a, aa, aaa, aaaa,
+  \ldots\}$.\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Concaténation de mots}
+
+{\footnotesize(Rappel : $\Sigma$ est un ensemble \emph{fini}, et
+  $\Sigma^*$ l'ensemble des \textbf{mots} sur $\Sigma$ = suites
+  finies.)\par}
+
+\medskip
+
+\itempoint Si $u = x_1\cdots x_m$ est un mot de longueur $m$,\\
+et $v = y_1\cdots y_n$ est un mot de longueur $n$,\\
+alors $uv := x_1\cdots x_m y_1\cdots y_n$ mot de longueur $m+n$.
+
+\medskip
+
+\itempoint On parle de \textbf{concaténation} ou simplement
+\textbf{produit} des mots $u$ et $v$.
+
+\medskip
+
+\itempoint Opération associative, $\varepsilon$ est neutre, et
+$|uv| = |u|+|v|$.
+
+\medskip
+
+\itempoint Puissances d'un mot : $u^n := u\cdots u$ (répété $n$ fois)
+si $u\in\Sigma^*$, $n\in\mathbb{N}$, avec conv\textsuperscript{n} $u^0
+:= \varepsilon$.  On a $u^{m+n} = u^m u^n$ et $u^{mn} = (u^m)^n$ et
+$|u^n| = n|u|$.
+
+\medskip
+
+\itempoint Si $w = uv$, on dit que $u$ est un \textbf{préfixe} de $w$,
+que $v$ est le \textbf{suffixe} correspondant.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Facteurs, sous-mots, miroir}
+
+\itempoint\textbf{Facteur} = préfixe d'un suffixe = suffixe d'un
+préfixe = choix de lettres consécutives.
+
+\smallskip
+
+Si $w = x_1\cdots x_n$, un facteur de $w$ est un $x_i x_{i+1}\cdots
+x_{j-1}$ où $i\leq j$ (longueur $j-i$), y compris le mot vide.
+
+\smallskip
+
+{\footnotesize P.ex. $\varepsilon$, $bbc$, $cab$ et $abbcab$ sont
+  facteurs de $abbcab$ mais pas $abc$.\par}
+
+\bigskip
+
+\itempoint\textbf{Sous-mot} = choix de lettres non
+nécess\textsuperscript{t} consécutives (mais dans l'ordre).
+
+\smallskip
+
+Si $w = x_1\cdots x_n$, un facteur de $w$ est un $x_{i_1} x_{i_2}
+\cdots x_{i_k}$ où $1\leq i_1<\cdots<i_k\leq n$ (longueur $k$), y
+compris le mot vide.
+
+\smallskip
+
+{\footnotesize P.ex. $\varepsilon$, $abc$ et $abbcab$ sont sous-mots
+  de $abbcab$ mais pas $cba$.\par}
+
+\smallskip
+
+{\footnotesize Tout facteur est un sous-mot.\par}
+
+\bigskip
+
+\itempoint\textbf{Mot miroir} = inverser l'ordre des lettres.
+
+\smallskip
+
+Si $w = x_1\cdots x_n$, alors $w^{\textsf{R}} := x_n\cdots x_1$.
+
+\smallskip
+
+{\footnotesize Noter $(uv)^{\textsf{R}} = v^{\textsf{R}}
+  u^{\textsf{R}}$.\par}
+
+\smallskip
+
+{\footnotesize \textbf{Palindrome} : mot $w$ tel que $w =
+  w^{\textsf{R}}$.\par}
+
+\end{frame}
+%
+\section{Langages et opérations sur les langages}
+\begin{frame}
+\frametitle{Notion de langage}
+
+\itempoint Un \textbf{langage} $L$ sur $\Sigma$ est un ensemble
+(quelconque !) de mots sur $\Sigma$.
+
+\smallskip
+
+Autrement dit, $L \subseteq \Sigma^*$ (rappel : $\Sigma^* =
+\{\text{mots sur~$\Sigma$}\}$).
+
+\medskip
+
+\itempoint Un langage peut être fini ou infini.
+
+\smallskip
+
+Deux cas extrêmes : $\varnothing$ (langage vide, ne contient aucun
+mot), $\Sigma^*$ (langage plein, contient tous les mots).
+
+\smallskip
+
+On distinguera bien $\{\varepsilon\}$ (contient un seul mot, le mot
+vide) et $\varnothing$ (ne contient aucun mot).
+
+\medskip
+
+{\footnotesize
+
+\itempoint Autres exemples sur $\Sigma = \{a,b\}$ : le langage $\{abb,
+abab, abbbb\}$, celui des mots commençant par $a$, celui des mots
+finissant par $b$, celui des mots ne contenant aucun $a$, celui des
+mots dont la longueur est un nombre premier.  Aussi $\Sigma$ = mots de
+longueur $1$.
+
+\par}
+
+\medskip
+
+\itempoint Opérations booléennes : $L_1\cup L_2$ (réunion), $L_1\cap
+L_2$ (intersection), $\Sigma^*\setminus L$ (complémentaire, parfois
+noté $\overline{L}$).
+
+{\footnotesize
+
+\itempoint Remarque : on a $L_1 \cap L_2 = \overline{\overline{L_1}
+  \cup \overline{L_2}}$.
+
+\par}
+
+\medskip
+
+{\footnotesize
+
+\itempoint On peut identifier un langage à une \textbf{propriété} des
+mots.
+
+\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Concaténation, puissances, étoile de Kleene}
+
+\itempoint Concaténation de langages : $L_1 L_2$ est l'ensemble $\{w_1
+w_2 : w_1\in L_1, w_2\in L_2\}$ des concaténations d'un mot quelconque
+de $L_1$ et d'un mot quelconque de $L_2$.
+
+\medskip
+
+\itempoint Puissances : $L^n := L\cdots L$ (avec $n$ facteurs) est
+l'ens. des concat\textsuperscript{ons} de $n$ mots de $L$.
+(Conv\textsuperscript{n} : $L^0 = \{\varepsilon\}$.)
+
+\medskip
+
+{\footnotesize
+
+\itempoint Attention : $L^n$ \alert{n'est pas} $\{w^n : w\in L\}$ en
+général.
+
+\par}
+
+\medskip
+
+\itempoint \textbf{Étoile de Kleene} : $L^* :=
+\bigcup_{n\in\mathbb{N}} L^n$ est l'ensemble des concaténations de
+mots de $L$ (éventuellement zéro).
+
+\smallskip
+
+{\footnotesize
+
+On retrouve bien $\Sigma^* = \{\text{mots sur~$\Sigma$}\}$.
+
+\par}
+
+\smallskip
+
+{\footnotesize
+
+\itempoint Variante : $L^+ := \bigcup_{n\geq 1} L^n = LL^*$ est
+l'ensemble des concaténations d'au moins un mot de $L$.
+
+Notamment, $\Sigma^+ = \{\text{mots non vides}\}$.
+
+\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Classes de langages}
+
+Une \textbf{classe de langages} est un ensemble de langages.  On ne
+fera pas leur théorie générale.
+
+\bigskip
+
+Mais on étudiera dans ce cours quatre grandes classes de langages, de
+la plus petite à la plus grande (inclusions successives) :
+
+\smallskip
+
+\itempoint Les \textbf{langages rationnels} définis par les
+expressions rationnelles.  Cette classe coïncidera avec celle des
+\textbf{langages reconnaissables} définis par les automates finis.
+
+\smallskip
+
+\itempoint Les \textbf{langages algébriques} définis par les
+grammaires hors contexte.
+
+\smallskip
+
+\itempoint Les \textbf{langages décidables} définis par des
+algorithmes quelconques (mais terminant à coup sûr en temps fini).
+
+\smallskip
+
+\itempoint Les \textbf{langages semi-décidables} définis par des
+algorithmes quelconques (terminant pour indiquer l'appartenance d'un
+mot au langage).
+
+\end{frame}
+%
+\section{Langages rationnels et expressions rationnelles}
+\begin{frame}
+\frametitle{Notion de langage rationnel}
+
+\itempoint Les \textbf{langages rationnels} sont ceux qui s'obtiennent
+à partir des langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$
+(pour $x\in\Sigma$) à partir des opérations de
+\begin{itemize}
+\item réunion (de deux langages),
+\item concaténation (de deux langages),
+\item étoile de Kleene (d'un langage),
+\end{itemize}
+appliquées un nombre fini de fois.
+
+\bigskip
+
+\itempoint Intuitivement, ce sont les langages qui admettent une
+description à partir des lettres de l'alphabet et des connecteurs « ou
+bien » (disjonction), « suivi de » (concaténation) et « répétitions
+illimitées de » (étoile).
+
+\bigskip
+
+\itempoint Exemple : $\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$
+est le langage constitué des mots formés d'un $d$ suivi d'une
+répétition quelconque de la lettre $c$.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Expressions rationnelles}
+
+\itempoint Les \textbf{expressions rationnelles}
+(= \textbf{régulières}) sont un moyen pour \emph{(dé)noter}
+commodément un langage rationnel.
+
+\smallskip
+
+{\footnotesize
+
+\itempoint P.ex. : $dc{*}$ est une r.e. dénotant le langage rationnel
+$\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$.  À lire comme « un
+$d$ suivi d'un nombre quelconque de $c$ ».
+
+\par}
+
+\medskip
+
+\itempoint Souvent utilisées en informatique pour spécifier des motifs
+de recherche.  (Nombreuses variations de syntaxe.)
+
+\medskip
+
+\itempoint Ce sont des mots sur l'alphabet « étendu » $\Sigma \cup
+\{\bot, \underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, les derniers
+étant appelés \textbf{métacaractères} (n'appartiennent pas
+à $\Sigma$).
+
+\medskip
+
+\itempoint Le ${|}$ dénote la disjonction (réunion des langages).
+
+\itempoint Le ${*}$ dénote l'étoile de Kleene.
+
+\itempoint Les parenthèses corrigent la priorité (étoile prioritaire
+sur concaténation prioritaire sur disjonction).
+
+\itempoint $\underline{\varepsilon}$ dénote le (langage formé du seul)
+mot vide.
+
+\itempoint $\bot$ dénote le langage vide (rarement utile...).
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Expressions rationnelles (suite)}
+
+Exemples d'expressions rationnelles sur $\Sigma = \{a,b,c,d\}$ :
+
+\begin{itemize}
+\item $a|b|cd$ dénote le langage $\{a\} \cup \{b\} \cup \{c\}\{d\} =
+  \{a,b,cd\}$.
+\item $a(b|cd)$ dénote le langage $\{a\}(\{b\} \cup \{c\}\{d\})
+  \penalty0 = \{a\}\{b,cd\} \penalty0 = \{ab,acd\}$, et est
+  équivalente à $ab|acd$.
+\item $a{*}$ dénote $\{a\}^* = \{\varepsilon, a, aa, aaa,\ldots\}$.
+\item $aa{*}$ dénote $\{a\}\{a\}^* = \{a, aa, aaa, aaaa,\ldots\} =
+  \{a\}^+$.
+\item $(a|b){*}$ dénote le langage $(\{a\}\cup\{b\})^* = \{a,b\}^*$
+  des mots quelconques sur l'alphabet $\{a,b\}$ (= mots ne contenant
+  que des $a$ et des $b$).
+\item $(a|bb){*}$ dénote le langage $\{a,bb\}^*$ des mots du précédent
+  dont les $b$ viennent par paires.
+\item $aba(a|b|c|d){*}$ ...mots ayant $aba$ pour
+  préfixe.
+\item $(a|b|c|d){*}aba$ ...mots ayant $aba$ pour suffixe.
+\item $(a|b|c|d){*}aba(a|b|c|d){*}$ ...mots ayant $aba$ pour facteur.
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Expressions rationnelles (suite)}
+
+Autres exemples d'expressions rationnelles sur $\Sigma =
+\{a,b,c,d\}$ :
+
+\begin{itemize}
+\item $(a|b|c|d){*}a(a|b|c|d){*}b(a|b|c|d){*}a(a|b|c|d){*}$ ...mots
+  ayant $aba$ pour sous-mot.
+\item $(ba{*}){*}$ dénote le langage $(\{b\}\{a\}^*)^* =
+  \{b,ba,baa,\ldots\}^*$ des mots formés d'un certain nombre de $b$
+  chacun suivi d'un certain nombre de $a$.
+\item $a{*}(ba{*}){*}$ est en fait équivalente à $(a|b){*}$
+  (dénotant le langage $\{a,b\}^*$).
+\item $(a|b)\underline{\varepsilon}(c|d)$ est équivalente à
+  $(a|b)(c|d)$ et dénote $\{ac,bc,ad,bd\}$.
+\item $(a|b)\bot(c|d)$ dénote le langage $\{a,b\} \varnothing \{c,d\}$
+  qui est vide.
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Expressions rationnelles : définition formelle}
+
+Formellement, par induction sur la complexité :
+
+\itempoint $\bot$ est une r.e. dénotant $\varnothing$,
+
+\itempoint $\underline{\varepsilon}$ est une r.e. dénotant
+$\{\varepsilon\}$,
+
+\itempoint si $x\in\Sigma$ alors $x$ est une r.e. dénotant $\{x\}$,
+
+\itempoint si $r_1,r_2$ sont deux r.e. dénotant $L_1$ et $L_2$
+alors $r_1 r_2$ est une r.e. dénotant $L_1 L_2$,
+
+\itempoint ...et $(r_1|r_2)$ est une r.e. dénotant $L_1\cup L_2$,
+
+\itempoint si $r$ est une r.e. dénotant $L$ alors $(r){*}$ est une
+r.e. dénotant $L^*$.
+
+\bigskip
+
+\itempoint Un langage rationnel est un langage dénoté par une r.e. ;
+si $r$ est une r.e., on note $L(r)$ le langage qu'elle dénote.
+
+\smallskip
+
+{\footnotesize
+
+(+ règles sur l'omission des parenthèses...)
+
+\par}
+
+\bigskip
+
+\itempoint On dit que $w$ \textbf{vérifie} $w$ quand $w \in L(r)$.
+
+\smallskip
+
+\itempoint On dit que $r$ et $r'$ sont \textbf{équivalentes} quand
+$L(r) = L(r')$.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Questions algorithmiques}
+
+On veut maintenant se poser les questions suivantes :
+
+\begin{itemize}
+\item Donnés $w$ (un mot) et $r$ (une r.e.), comment décider
+  algorithm\textsuperscript{t} si $w \in L(r)$ ?
+\item Données $r$ et $r'$ (deux r.e.), comment décider
+  algorithm\textsuperscript{t} si $L(r) = L(r')$ ?
+\item Donnée $r$, existe-t-il une r.e. $r'$ telle que $L(r') =
+  \Sigma^* \setminus L(r)$ (i.e., le langage complémentaire d'un
+  rationnel est-il rationnel) et si oui, comment la trouver
+  algorithm\textsuperscript{t} ?
+\item Données $r_1$ et $r_2$, existe-t-il une r.e. $r$ telle que $L(r)
+  = L(r_1) \cap L(r_2)$ (i.e., l'intersection de deux langages
+  rationnels est-il rationnel) et si oui, comment la trouver
+  algorithm\textsuperscript{t} ?
+\end{itemize}
+
+La résolution de ces problèmes passera par la notion
+d'\textbf{automate fini}.
+
+\end{frame}
+%
+\end{document}