{\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