%% 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}