path: root/slides1.tex

%% 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\}^* = \{\varepsilon, 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} $r$ 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}