diff options
| -rw-r--r-- | notes-inf105.tex | 294 |
1 files changed, 260 insertions, 34 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 939abe7..21d4d82 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1,6 +1,6 @@ %% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} -\usepackage[a4paper,hmargin=2cm,vmargin=3cm]{geometry} +\usepackage[a4paper,hmargin=2.5cm,vmargin=3cm]{geometry} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} @@ -29,7 +29,7 @@ \theoremstyle{definition} \newtheorem{comcnt}{Tout}[subsection] \newcommand\thingy{% -\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} } \newtheorem{defn}[comcnt]{Définition} \newtheorem{prop}[comcnt]{Proposition} \newtheorem{lem}[comcnt]{Lemme} @@ -88,6 +88,7 @@ Git: \input{vcline.tex} \pretolerance=8000 \tolerance=50000 +\linepenalty=5 % Default is supposedly 10 % @@ -121,6 +122,8 @@ une application informatique pratique à l'analyse de textes ou de chaînes de caractères (qu'on appellera par la suite « mots », cf. §\ref{subsection-introduction-and-words}). +\smallbreak + Après des définitions générales (sections \ref{subsection-introduction-and-words} à \ref{subjection-languages}), ces notes sont divisées en grandes parties (inégales) de la manière @@ -139,6 +142,8 @@ suivante : théoriques sur ce qu'un algorithme peut faire. \end{itemize} +\smallbreak + À ces parties seront associées la définition de différentes classes de « langages » (voir §\ref{subjection-languages} pour la définition de ce terme) qu'il s'agit d'étudier : @@ -209,6 +214,8 @@ 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}. +\smallskip + L'alphabet sera généralement fixé une fois pour toutes dans la discussion, et désigné par la lettre $\Sigma$ (sigma majuscule). @@ -228,6 +235,8 @@ caractères : on écrira donc \texttt{\char`\"foobar\char`\"} pour parler du mot en question. Dans ces notes, nous utiliserons peu cette convention.) +\medskip + L'ensemble de tous les mots sur un alphabet $\Sigma$ sera désigné $\Sigma^*$ (on verra en \ref{kleene-star} ci-dessous cette notation comme un cas particulier d'une construction « étoile » plus @@ -236,6 +245,8 @@ l'ensemble (infini !) dont les éléments sont toutes les suites finies binaires (= suites finies de $0$ et de $1$). Ainsi, écrire « $w \in \Sigma^*$ » signifie « $w$ est un mot sur l'alphabet $\Sigma$ ». +\medskip + {\footnotesize\thingy Typographiquement, on essaiera autant que possible de désigner des mots par des variables mathématiques telles que $u,v,w$, tandis que $x,y,z$ désigneront plutôt des lettres @@ -369,6 +380,8 @@ fois du mot $w$. Formellement, on définit par récurrence : peut constater que $w^r w^s = w^{r+s}$ quels que soient $r,s\in\mathbb{N}$.) On a bien sûr $|w^r| = r|w|$. +\smallskip + Cette définition sert notamment à désigner de façon concise les mots comportant des répétitions d'une même lettre : par exemple, le mot $aaaaa$ peut s'écrire tout simplement $a^5$, et le mot $aaabb$ peut @@ -405,6 +418,8 @@ produire que le préfixe et le suffixe de longueur $k$ soient égaux pour d'autres $k$ que $0$ et $|w|$, comme le montre l'exemple qui suit.) +\smallskip + À titre d'exemple, le mot $abbcab$ sur l'alphabet $\Sigma=\{a,b,c,d\}$ a les sept préfixes suivants, rangés par ordre croissant de longueur : $\varepsilon$ (le mot vide), $a$, $ab$, $abb$, $abbc$, $abbca$ et @@ -421,11 +436,15 @@ et si $w = u_0 v u_1$ est leur concaténation, on dira que $v$ est un est déterminé simplement par sa longueur, un facteur est déterminé par sa longueur et l'emplacement à partir duquel il commence. +\smallskip + À titre d'exemple, les facteurs du mot $abbcab$ sont : $\varepsilon$ (le mot vide), $a$, $b$, $c$, $ab$, $bb$, $bc$, $ca$, $abb$, $bbc$, $bca$, $cab$, $abbc$, $bbca$, $bcab$, $abbca$, $bbcab$ et $abbcab$ lui-même. +\smallskip + Dans un contexte informatique, ce que nous appelons ici « facteur » est souvent appelé « sous-chaîne [de caractères] ». Il ne faut cependant pas confondre ce concept avec celui de sous-mot défini @@ -439,6 +458,8 @@ certaines lettres du mot $w$, dans le même ordre, mais en en effaçant d'autres ; à la différence du concept de facteur, celui de sous-mot n'exige pas que les lettres gardées soient consécutives. +\smallskip + À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$ (obtenu en gardant les lettres soulignées ici : $\underline{a}bb\underline{c}a\underline{b}$ ; pour se rattacher à la @@ -475,6 +496,8 @@ d'exemple, $(ababb)^{\textsf{R}} = bbaba$. On remarquera que $(w_1 w_2)^{\textsf{R}} = w_2^{\textsf{R}} w_1^{\textsf{R}}$ si $w_1,w_2$ sont deux mots quelconques. +\smallskip + Un mot $w$ est dit \defin{palindrome} lorsque $w = w^{\textsf{R}}$. Par exemple, $abba$ est un palindrome sur $\{a,b,c,d\}$ (ou bien le mot « ressasser » sur l'alphabet du français). @@ -563,11 +586,15 @@ langage qu'on vient d'associer l'un à l'autre (par exemple, le langage des mots commençant par $a$ et la propriété « commencer par $a$ »), un langage pourrait être considéré comme une propriété des mots. -{\footnotesize(Ceci n'a rien de spécifique aux langages : une partie - d'un ensemble $E$ quelconque peut être identifiée à une propriété - que les éléments de $E$ peuvent ou ne pas avoir, à savoir, +\smallskip + +{\footnotesize(Ce qui précède n'a rien de spécifique aux langages : + une partie d'un ensemble $E$ quelconque peut être identifiée à une + propriété que les éléments de $E$ peuvent ou ne pas avoir, à savoir, appartenir à la partie en question.)\par} +\smallskip + On évitera de faire cette identification pour ne pas introduire de complication, mais il est utile de la garder à l'esprit : par exemple, dans un langage de programmation fonctionnel, un « langage » au sens @@ -583,6 +610,8 @@ $L_1,L_2 \subseteq \Sigma^*$), on peut former les langages sont simplement les opérations ensemblistes usuelles (entre parties de $\Sigma^*$). +\smallskip + Les opérations correspondantes sur les propriétés de mots sont respectivement le « ou logique » (=disjonction) et le « et logique » (=conjonction) : à titre d'exemple, sur $\Sigma = \{a,b\}$ si $L_1$ @@ -600,6 +629,8 @@ simplement l'ensemble des mots sur $\Sigma$ \emph{n'appartenant pas} à $L$. L'opération correspondante sur les propriétés de mots est la négation logique. +\smallskip + À titre d'exemple, sur $\Sigma=\{a,b\}$, si $L$ est le langage des mots commençant par $a$, alors $\overline{L}$ est le langage des mots ne commençant pas par $a$, c'est-à-dire, la réunion de @@ -620,6 +651,8 @@ L_1 L_2 &:= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\ \end{aligned} \] +\smallskip + À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L_1 = \{a,bb\}$ et $L_2 = \{bc, cd\}$ alors $L_1 L_2 = \{abc, acd, bbbc, bbcd\}$. @@ -635,10 +668,14 @@ récurrence : \item $L^{r+1} = L^r L$. \end{itemize} +\smallskip + À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L = \{a,bb\}$, alors $L^2 = \{aa, abb, bba, bbbb\}$ et $L^3 = \{aaa, aabb, abba, abbbb, \penalty-100 bbaa, bbabb, bbbba, bbbbbb\}$. +\medskip + \emph{Attention}, $L^r$ n'est pas le langage $\{w^r : w\in L\}$ constitué des répétitions $r$ fois ($w^r$) des mots $w$ de $L$ : c'est le langage des concaténations de $r$ mots appartenant à $L$ \emph{mais @@ -661,17 +698,23 @@ L^* &:= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\ \end{aligned} \] +\smallskip + À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L = \{a,bb\}$, alors on a $L^* = \{\varepsilon, a, bb, \penalty-200 aa, abb, bba, bbbb, \penalty-200 aaa, aabb, abba, abbbb, \penalty-100 bbaa, bbabb, bbbba, bbbbbb, \ldots\}$. +\smallskip + Comme ci-dessus, il faut souligner que les mots $w_1,\ldots,w_r$ concaténés n'ont pas à être égaux : notamment, $\{a,b\}^*$ est le langage constitué de tous les mots sur l'alphabet $\{a,b\}$, pas le langage $\{a\}^* \cup \{b\}^*$ constitué des mots obtenus en répétant la lettre $a$ ou en répétant la lettre $b$. +\smallskip + On remarquera que la définition de $L^*$ ci-dessus redonne bien, lorsqu'on l'applique à l'alphabet $\Sigma$ lui-même (considéré comme langage des mots de longueur $1$), l'ensemble $\Sigma^*$ de tous les @@ -697,7 +740,7 @@ langage sur l'alphabet $\Sigma$, on définit le langage miroir $L^{\mathsf{R}}$ comme l'ensemble des mots miroirs des mots de $L$, c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$. -\medbreak +\bigbreak \thingy\label{set-of-languages} De même que l'ensemble des mots sur un alphabet $\Sigma$ admet une notation, à savoir $\Sigma^*$, on peut @@ -712,6 +755,8 @@ synonyme de « $L\subseteq \Sigma^*$ » ou de « $L$ est un langage sur $\Sigma$ » ; on évitera cependant de le faire, car cette notation est plus lourde qu'utile. +\smallskip + {\footnotesize Il sera marginalement question dans ces notes de « classes de langages » : une classe de langages est un ensemble de langages (c'est-à-dire une partie de $\mathscr{P}(\Sigma^*)$, ou si @@ -769,6 +814,8 @@ cf. \ref{concatenation-of-languages}), et l'étoile de Kleene (représentant une répétition quelconque d'un certain motif, cf. \ref{kleene-star}). +\medskip + L'importance des langages rationnels, et des expressions rationnelles (=régulières) qui les décrivent, vient : \begin{itemize} @@ -786,6 +833,8 @@ L'importance des langages rationnels, et des expressions rationnelles une chaîne de caractères. \end{itemize} +\smallskip + Passons maintenant à une définition plus précise. \bigbreak @@ -821,6 +870,8 @@ concaténation de deux langages rationnels, et l'étoile de Kleene d'un langage rationnel, sont rationnels ; et les langages rationnels sont exactement ceux qu'on obtient ainsi à partir des langages de base. +\smallskip + À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage $\{c\}$ (constitué du seul mot $c$) est rationnel, son étoile de Kleene, c'est-à-dire $\{c\}^* = \{\varepsilon, c, cc, ccc, @@ -854,6 +905,8 @@ ensembles $\mathscr{C}$ vérifiant tous ces propriétés, est la classe $\mathscr{R}$ des langages rationnels (et un langage rationnel est simplement un élément de $\mathscr{R}$). +\medskip + \emph{Attention !}, le fait que la classe $\mathscr{R}$ des langages rationnels soit stable par concaténation signifie que si $L_1$ et $L_2$ sont rationnels alors le langage $L_1 L_2$ (constitué de tous @@ -876,6 +929,8 @@ langage « dénoté par l'expression rationnelle $dc{*}$ ». Ceci fournit du même coup une nouvelle définition des langages rationnels : ce sont les langages dénotés par une expression rationnelle. +\smallskip + Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$) est un mot sur l'alphabet $\Sigma \cup \{\bot, \underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, où $\bot, @@ -949,7 +1004,8 @@ $\Sigma = \{a,b,c,d\}$ : \item l'expression rationnelle $(bc){*}$ dénote le langage $\{bc\}^* = \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; \item l'expression rationnelle $(a|(bc){*})$ dénote le langage $\{a\} - \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; + \cup \{bc\}^* = \{a,\penalty0 \varepsilon,\penalty1000 + bc,\penalty1000 bcbc,\penalty1000 bcbcbc, \ldots\}$ ; \item l'expression rationnelle $(a|(bc){*})d$ dénote le langage $\{a, d, bcd, bcbcd, bcbcbcd, \ldots\}$ ; \item l'expression rationnelle $\bot d$ dénote le langage @@ -1364,6 +1420,8 @@ se trouve l'automate une fois qu'il a consommé le mot $w$, on dira que l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in F$ ou que $q_n \not\in F$. +\smallskip + Graphiquement, on peut présenter la procédure de la manière suivante : on part de l'état $q_0$ (sommet du graphe représentant l'automate) indiqué par la flèche entrante (pointant de nulle part), et pour @@ -1419,11 +1477,15 @@ $\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il \textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par l'automate $A$. +\smallskip + Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la forme du langage $L(A)$ accepté par un DFA $A$ s'appelle \defin[reconnaissable (langage)]{reconnaissable} (sous-entendu : par automate déterministe fini). +\smallskip + On dit que deux DFA $A,A'$ sont \defin[équivalents (automates)]{équivalents} lorsqu'ils reconnaissent le même langage, i.e., $L(A) = L(A')$. @@ -1474,6 +1536,8 @@ certain mot). Dans le cas contraire, l'état est dit modifier) les états inaccessibles dans un DFA ne change rien au langage reconnu (on obtient des automates équivalents). +\smallskip + Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible (l'automate est donc équivalent à celui représenté en \ref{discussion-example1}). On remarquera qu'il ne change rien que @@ -1538,6 +1602,8 @@ en \ref{definition-dfa} est que la fonction $\delta$ est partielle, ce qui signifie qu'elle n'est pas obligatoirement définie sur tout couple $(q,x) \in Q\times\Sigma$. +\smallskip + Un DFA est considéré comme un DFAi particulier où la fonction de transition $\delta$ se trouve être définie partout. @@ -1546,6 +1612,8 @@ différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y a maintenant \emph{au plus une} (et non plus exactement une) arête partant de $q$ et étiquetée par $x$. +\smallskip + L'intérêt informatique des DFAi est de ne pas s'obliger à stocker inutilement des transitions et des états inutiles au sens où ils ne permettront jamais d'accepter le mot (voir la notion d'automate @@ -1564,6 +1632,8 @@ fonctionner : l'automate n'a plus d'état, n'effectue plus de transition, et n'acceptera pas le mot quelles que soient les lettres ultérieures. +\smallskip + Cela revient une fois de plus à dire que le mot $w$ est accepté lorsqu'il existe un chemin orienté dans l'automate, reliant l'état $q_0$ initial à un état $q_n$ final, et tel que le mot $w = x_1 \cdots @@ -1595,6 +1665,8 @@ Enfin, l'automate $A$ accepte un mot $w$ lorsque $\delta^*(q_0,w)$ soit parce que $\delta^*(q_0,w)$ n'est pas défini ou parce qu'étant défini il n'appartient pas à $F$), l'automate rejette le mot. +\smallskip + Le langage accepté $L(A)$ et l'équivalence de deux automates sont définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). @@ -1707,6 +1779,8 @@ DFAi représenté en \ref{discussion-example2b} : accessible d'un DFAi comme pour un DFA (cf. \ref{definition-dfa-accessible-state}). +\smallskip + On dira en outre d'un état $q$ d'un DFAi qu'il est \defin[co-accessible (état)]{co-accessible} lorsqu'il existe un mot $w \in \Sigma^*$ tel que $\delta(q,w)$ soit défini et soit final, @@ -1720,6 +1794,8 @@ DFAi elle présente l'intérêt qu'on peut supprimer les états non co-accessibles dans un DFAi (ainsi, bien sûr, que toutes les transitions qui y conduisent). +\smallskip + Un DFAi dont tous les états sont à la fois accessibles et co-accessibles (on les dit aussi \defin[utile (état)]{utiles}) est parfois appelé \defin[émondé (automate)]{émondé}. On peut émonder un @@ -1818,6 +1894,8 @@ lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0 \in I$ et $q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq n$. +\smallskip + La différence cruciale avec les DFAi est donc que, maintenant, il pourrait exister plusieurs chemins possibles partant d'un état initial dont les transitions sont étiquetées par les lettres du même mot. @@ -1835,6 +1913,8 @@ un chemin orienté conduisant de $q$ à $q'$ et tel que le mot $w$ soit obtenu en lisant dans l'ordre les étiquettes des différentes arêtes de ce chemin. +\smallskip + Formellement : si $A = (Q,I,F,\delta)$ est un NFA sur l'alphabet $\Sigma$, on définit une relation $\delta^* \subseteq Q \times \Sigma^* \times Q$ par $(q,w,q') \in \delta^*$ lorsque $w = @@ -1850,9 +1930,12 @@ de $w$) : \end{itemize} Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$ -et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. Le -langage accepté $L(A)$ et l'équivalence de deux automates sont définis -de façon analogue aux DFA +et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. + +\smallskip + +Le langage accepté $L(A)$ et l'équivalence de deux automates sont +définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). \thingy\label{discussion-example4} Pour illustrer le fonctionnement @@ -1889,7 +1972,7 @@ l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera l'avant-dernière lettre, et, dans ce cas, passe dans l'état $1$ pour pouvoir accepter le mot. -\medbreak +\bigbreak Comme les DFAi avant eux, les NFA sont en fait équivalents aux DFA ; mais cette fois-ci, le coût algorithmique de la transformation peut @@ -1942,6 +2025,8 @@ se voir à travers sa fonction indicatrice, qui est une fonction $Q \to procédure décrite dans la démonstration de cette proposition en ne gardant que les états accessibles. +\smallskip + Algorithmiquement, la déterminisation de $A$ s'obtient par la procéduire suivante : \begin{itemize} @@ -2065,17 +2150,22 @@ est la donnée \item d'une relation de transition $\delta \subseteq Q \times (\Sigma\cup\{\varepsilon\}) \times Q$. \end{itemize} + Autrement dit, on autorise maintenant des transitions étiquetées par le mot vide $\varepsilon$ plutôt que par une lettre $x \in\Sigma$ : ces transitions sont dites \defin[spontanée (transition)]{spontanées}, ou \index{epsilon-transition@$\varepsilon$-transition|see{spontanée}}\textbf{ε-transitions}. +\smallskip + Soulignons qu'on ne définit les ε-transitions \emph{que} pour les automates non-déterministes : ou, pour dire les choses autrement, \emph{un automate qui possède des ε-transitions est par nature même non-déterministe}. +\smallskip + La représentation graphique des εNFA est évidente (on utilisera le symbole « $\varepsilon$ » pour étiqueter les transitions spontanées). Un NFA est considéré comme un εNFA particulier pour lequel il n'y a @@ -2089,6 +2179,8 @@ pourquoi un automate à transition spontanée est forcément non-déterministe : ces transitions spontanées ne sont qu'une \emph{possibilité}, ce qui sous-entend le non-déterminisme.) +\smallskip + De façon plus précise, un εNFA accepte un mot $w$ lorsqu'\emph{il existe} un chemin orienté conduisant d'un état initial $q_0$ à un état final $q_n$ et tel que $w$ coïncide avec le mot obtenu en lisant @@ -2117,9 +2209,12 @@ $(q_{i-1},t_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w = t_1\cdots t_n$. Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$ -et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. Le -langage accepté $L(A)$ et l'équivalence de deux automates sont définis -de façon analogue aux DFA +et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. + +\smallskip + +Le langage accepté $L(A)$ et l'équivalence de deux automates sont +définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). \thingy\label{discussion-example5} Voici un exemple de εNFA @@ -2161,6 +2256,8 @@ l'exemple \ref{discussion-example5} ci-dessus, on a $C(0) = \{0,1,2\}$ et $C(1) = \{1,2\}$ et $C(2) = \{2\}$. Dans tout NFA sans ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.) +\smallskip + Il est clair qu'on peut calculer algorithmiquement $C(q)$ (par exemple par un algorithme de Dijkstra / parcours en largeur, sur le graphe orienté dont l'ensemble des sommets est $Q$ et l'ensemble des arêtes @@ -2322,6 +2419,8 @@ un DFA $A$ tel que $L = L(A)$. D'après \ref{completion-of-dfai}, on peut remplacer « DFA » dans cette définition par « DFAi », « NFA » ou « εNFA » sans changer la définition. +\smallskip + Nous allons maintenant montrer que les langages reconnaissables sont stables par différentes opérations. Dans cette section, nous traitons le cas des opérations booléennes (complémentaire, union, intersection) @@ -2464,6 +2563,8 @@ en \ref{rational-languages-are-recognizable} que les langages rationnels sont reconnaissables (la réciproque faisant l'objet de la section \ref{subsection-rnfa-and-kleenes-algorithm}). +\smallskip + Pour établir ces stabilités, on va travailler sur les NFA et utiliser la construction parfois appelée « de Glushkov » ou « automate standard » ; ceci fournira un « automate de Glushkov » pour chaque @@ -2529,7 +2630,7 @@ $q_0$ vers chacun des états qui étaient initiaux dans $A$, puis en résultat que ce qui vient d'être dit.) \end{proof} -\medbreak +\bigbreak On a vu en \ref{dfa-union-and-intersection} une preuve, à base de DFA, que $L_1 \cup L_2$ est reconnaissable lorsque $L_1$ et $L_2$ le sont. @@ -2889,6 +2990,8 @@ de base décrits en \ref{trivial-standard-automata} et en appliquant les constructions décrites dans les démonstrations de \ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. +\medskip + Plus exactement, on associe à chaque expression rationnelle $r$ (sur un alphabet $\Sigma$ fixé) un automate $A_r$ standard, appelé \defin[Glushkov (construction d'automate de)]{automate de Glushkov}, @@ -2911,6 +3014,8 @@ définie en \ref{regular-expressions}) : de \ref{nfa-star}. \end{itemize} +\smallskip + Cette automate de Glushkov $A_r$ possède les propriétés suivantes : \begin{itemize} \item c'est un NFA reconnaissant le langage $L(r)$ dénoté par @@ -3071,6 +3176,8 @@ Elle possède pour sa part les propriétés suivantes : concaténation implicite). \end{itemize} +\smallskip + Dans les dessins qui suivent, on symbolisera de la manière suivante un automate de Thompson $A$ quelconque : \begin{center} @@ -3193,11 +3300,13 @@ très simple à appliquer ; mais elle conduit à des automates rapidement énormes, comportant un nombre considérable d'états et de transitions spontanées « stupides ». +\medskip + À titre d'exemple, voici l'automate de Thompson, déjà gros, de l'expression rationnelle $(a|b){*}b$ : \begin{center} -\scalebox{0.75}{% +\scalebox{0.70}{% %%% begin example9 %%% \begin{tikzpicture}[>=latex,line join=bevel,automaton] @@ -3237,6 +3346,7 @@ dans $(a|b){*}b$.) Pour comparaison, voici son automate de Glushkov : \begin{center} +\scalebox{0.85}{% %%% begin example9b %%% \begin{tikzpicture}[>=latex,line join=bevel,automaton] @@ -3265,6 +3375,7 @@ Pour comparaison, voici son automate de Glushkov : \end{tikzpicture} %%% end example9b %%% +} \end{center} Il a $4$ états puisqu'il y a $3$ lettres dans $(a|b){*}b$. Ces états @@ -3314,6 +3425,7 @@ alphabet $\Sigma$ est la donnée $(\mathrm{regexp}(\Sigma))$ désigne l'ensemble des expressions rationnelles sur $\Sigma$. \end{itemize} + Autrement dit, on autorise maintenant des transitions étiquetées par des expressions rationnelles quelconques sur $\Sigma$. Remarquons qu'on doit maintenant demander \emph{explicitement} que l'ensemble @@ -3336,9 +3448,12 @@ transitions ($w = v_1\cdots v_n$), chacun vérifiant l'expression rationnelle qui étiquette la transition (soit $v_i \in L(r_i)$). Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$ -et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. Le -langage accepté $L(A)$ et l'équivalence de deux automates sont définis -de façon analogue aux DFA +et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. + +\smallskip + +Le langage accepté $L(A)$ et l'équivalence de deux automates sont +définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). \thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAi ou DFA) est @@ -3347,12 +3462,16 @@ considéré comme un RNFA particulier dont les transitions sont rationnelle) soit par le symbole $\underline{\varepsilon}$ (dénotant le langage $\{\varepsilon\}$) dans le cas des transitions spontanées. +\smallskip + Une expression rationnelle $r$ peut aussi être considérée comme un RNFA particulier comportant un unique état initial, un unique état final, et une unique transition de l'un vers l'autre, étiquetée par l'expression $r$ elle-même. Il est évident que ce RNFA reconnaît exactement le langage dénoté par $r$. +\smallskip + La représentation graphique des RNFA ne pose pas de problème particulier (voir en \ref{example-of-state-elimination} pour différents exemples). @@ -3369,6 +3488,8 @@ S'il n'y a \emph{aucune} transition de $q$ vers $q'$, on peut toujours choisir d'en ajouter une $(q,\bot,q')$ (qui ne peut pas être empruntée !) si c'est commode. +\medskip + Comme les εNFA, les NFA et les DFAi avant eux, les RNFA peuvent se ramener aux automates précédemment définis : @@ -3423,6 +3544,8 @@ chemin dans ce dernier, suivi d'une transition spontanée depuis un état final de $A_{r_j}$. \end{proof} +\medskip + Mais la surprise des RNFA est qu'ils peuvent aussi se ramener à des expressions rationnelles ! @@ -3617,7 +3740,7 @@ conduit à l'automate suivant : \noindent et finalement à l'expression rationnelle $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente. -\medbreak +\bigbreak \thingy Donnons encore l'exemple du DFAi suivant : @@ -3683,6 +3806,8 @@ reconnaissables coïncident. (On pourra donc considérer ces termes comme synonymes.) \end{thm} +\smallskip + Il faut cependant retenir que s'il y a, mathématiquement, équivalence entre ces deux classes de langages, cette équivalence \emph{a un coût algorithmique}, c'est-à-dire que la conversion d'une expression @@ -3705,6 +3830,8 @@ d'expressions rationnelles $r_1,r_2$, de fabriquer algorithmiquement une expression rationnelle $r''$ (« conjonction » de $r_1$ et $r_2$) qui dénote le langage intersection de ceux dénotés par $r_1$ et $r_2$. +\smallskip + Le coût de ces opérations, cependant, est astronomique : doublement exponentiel, puisqu'il s'agit de convertir l'expression en NFA, de déterminiser le NFA en DFA (à un premier coût exponentiel), @@ -3864,6 +3991,8 @@ langage $L$ n'est pas rationnel est donc quelque chose comme ceci : être). \end{itemize} +\smallskip + Donnons maintenant un exemple d'utilisation du lemme : \begin{prop}\label{example-of-pumping-lemma} @@ -3909,6 +4038,8 @@ n'avons pas donné de réponse : comment savoir si deux automates \emph{donnés} ou deux expressions rationnelles données (ou un de chaque) sont équivalents ? +\smallskip + Pour cela, on va introduire un DFA particulier, \emph{canonique}, associé à un langage rationnel, qu'on pourra calculer algorithmiquement, et qui sera véritablement associé au langage, @@ -4099,8 +4230,9 @@ chaque classe d'équivalence pour $\equiv$. \thingy L'algorithme décrit par la proposition \ref{dfa-minimization} porte le nom d'algorithme \index{Moore (algorithme de)|see{minimisation}}\textbf{de Moore} ou \defin[minimisation - (algorithme de)]{de minimisation} ou \textbf{de réduction}. Voici -comment on peut le mettre en œuvre de façon plus concrète : + (algorithme de)]{de minimisation} ou \textbf{de réduction}. + +Voici comment on peut le mettre en œuvre de façon plus concrète : \begin{itemize} \item s'assurer qu'on a affaire à un DFA \underline{\emph{complet sans état inaccessible}} (si nécessaire, déterminiser l'automate s'il @@ -4126,6 +4258,8 @@ comment on peut le mettre en œuvre de façon plus concrète : du représentant). \end{itemize} +\smallskip + La dernière étape (construction de l'automate) permet de vérifier qu'on a correctement terminé l'étape précédente (raffinement de la partition) : si deux états dans la même classe ont une transition @@ -4201,6 +4335,8 @@ $\{2,3\}$ et $\{4,5\}$, et à l'automate minimal suivant : %%% end example7m %%% \end{center} +\medskip + Il est intéressant de voir comment des petits changements sur l'automate initial modifient la minimisation. Si on fait pointer la transition étiquetée par $c$ de l'état $1$ vers lui-même (au lieu @@ -4340,6 +4476,8 @@ l'analyse des langues naturelles ; mais c'est plus en informatique qu'en linguistique qu'elles ont trouvé leur utilité, à commencer surtout par la définition de la syntaxe du langage ALGOL 60. +\smallskip + Cette fois-ci, on ne s'intéressera pas simplement au langage défini (par la grammaire hors contexte, dit langage « algébrique »), mais aussi à la manière dont ces mots s'obtiennent par la grammaire, et @@ -4369,6 +4507,8 @@ d'une nouvelle instruction, et enfin un $\mathtt{fi}$ ; pour définir un bloc ($\mathit{Block}$), on peut soit ne rien mettre du tout, soit mettre une instruction suivi d'un nouveau bloc ». +\smallskip + Notre but va être d'expliquer quel genre de règles de ce genre on peut autoriser, comment elles se comportent, quels types de langages elles définissent, et comment on peut analyser (essentiellement, retrouver @@ -4429,6 +4569,8 @@ lorsqu'ils appartiennent à $N$. Un mot sur $\Sigma\cup N$ désigner un mot sur $\Sigma$ (autrement dit, un mot est un pseudo-mot ne comportant que des symboles terminaux). +\smallskip + Pour redire les choses autrement, les symboles terminaux sont les lettres des mots du langage qu'on cherche à définir ; les symboles nonterminaux sont des symboles qui servent uniquement à titre @@ -4437,6 +4579,8 @@ disparaître finalement. Un « pseudo-mot » est un mot pouvant contenir des nonterminaux, tandis qu'un « mot » sans précision du contraire ne contient que des terminaux. +\medskip + {\footnotesize Typographiquement, on aura tendance à utiliser des lettres minuscules pour désigner les symboles terminaux, et majuscules pour désigner les symboles nonterminaux ; et on aura @@ -4463,6 +4607,8 @@ $T \mathrel{\rightarrow_G} \alpha$, ou simplement $T \rightarrow \alpha$ (lorsque $G$ est clair) pour signifier que $(T,\alpha)$ est une règle de $G$. +\smallskip + On définit une relation $\Rightarrow$ en posant $\gamma T \gamma' \Rightarrow \gamma\alpha\gamma'$ pour toute règle $(T,\alpha)$ et tous pseudo-mots $\gamma,\gamma'$ : autrement dit, formellement, on définit @@ -4494,6 +4640,8 @@ précisera la grammaire appliquée en écrivant $\lambda \mathrel{\Rightarrow_G} \xi$ au lieu de simplement $\lambda\Rightarrow\xi$. +\smallskip + Une suite de pseudo-mots $(\lambda_0,\ldots,\lambda_n)$ telle que \[ \lambda_0 \Rightarrow \lambda_1 \Rightarrow \cdots \Rightarrow \lambda_n @@ -4517,6 +4665,8 @@ qu'on peut passer de $\lambda$ à $\xi$ en effectuant une suite chaque étape un nonterminal $T$ par la partie droite $\alpha$ d'une règle $T \rightarrow \alpha$ de la grammaire $G$. +\smallskip + Il va de soi qu'un pseudo-mot qui ne comporte que des terminaux, i.e., qui est en fait un mot (sur $\Sigma$), ne peut pas être dérivé plus loin. Ceci justifie au moins en partie la terminologie de @@ -4530,11 +4680,15 @@ de l'axiome $S$ de $G$, autrement dit : L(G) = \{w \in \Sigma^* : S \mathrel{\Rightarrow^*} w\} \] +\smallskip + Un langage qui peut s'écrire sous la forme $L(G)$ où $G$ est une grammaire hors contexte est appelé \index{hors contexte (langage)|see{algébrique}}\textbf{langage hors contexte} ou \defin[algébrique (langage)]{algébrique}. +\smallskip + Deux grammaires hors contexte $G$ et $G'$ sont dites \defin[faiblement équivalentes (grammaires)]{faiblement équivalentes} ou \index{langage-équivalentes (grammaires)|see{faiblement @@ -4575,6 +4729,8 @@ S b^n \Rightarrow a^n b^n Le langage $L(G)$ défini par la grammaire est donc $\{a^n b^n : n\in\mathbb{N}\}$. +\smallskip + On a vu en \ref{example-of-pumping-lemma} que ce langage n'est pas rationnel : il existe donc des langages algébriques qui ne sont pas rationnels. En revanche, pour ce qui est de la réciproque, on verra @@ -4599,6 +4755,8 @@ langage défini par la grammaire est l'ensemble de tous les mots (sans nonterminaux) qui peuvent s'obtenir par application des règles de remplacement à partir de l'axiome. +\smallskip + Les grammaires de types 0 et 1, avec celles de type 2 c'est-à-dire hors contexte, et celles de type 3 (= régulières) qui seront définies en \ref{regular-grammar} ci-dessous, forment une hiérarchie (plus le @@ -4611,7 +4769,7 @@ classe de langages définie est petite) appelée \defin[Chomsky \begin{prop}\label{rational-languages-are-algebraic} Tout langage rationnel est algébrique. Mieux, on peut déduire -algorithmiquement une grammaire hors contexte $G$ d'un εNFA $A$ de +algo\-ri\-thmi\-quement une grammaire hors contexte $G$ d'un εNFA $A$ de façon à avoir $L(G) = L(A)$. \end{prop} \begin{proof} @@ -4785,6 +4943,8 @@ en \ref{example-of-pumping-lemma-for-algebraic-languages}. En conséquence, il n'est pas non plus vrai en général que le complémentaire d'un langage algébrique soit algébrique. +\smallskip + En revanche, le fait suivant, que nous admettons sans démonstration, peut s'avérer utile : @@ -5003,6 +5163,8 @@ suivantes : \end{itemize} \end{itemize} +\smallskip + On dit de plus que l'arbre est \textbf{complet}, ou simplement qu'il s'agit d'un arbre d'analyse, lorsqu'il vérifie la propriété supplémentaire suivante : @@ -5166,10 +5328,14 @@ une dérivation dans laquelle le symbole réécrit est toujours \emph{le chaque dérivation immédiate la constituant ne comporte que des symboles terminaux. +\smallskip + À titre d'exemple, les deux dérivations données en \ref{example-of-derivations} sont respectivement une dérivation gauche et une dérivation droite. +\smallskip + À chaque arbre d'analyse est associée une et une seule dérivation gauche : on l'obtient de façon évidente en réécrivant à chaque étape le symbole nonterminal le plus à gauche en suivant la règle indiquée @@ -5192,6 +5358,8 @@ L(G)$ a un unique arbre d'analyse ; il revient au même de dire que tout mot de $L(G)$ a une unique dérivation droite, ou encore que tout mot de $L(G)$ a une unique dérivation gauche. +\smallskip + Les grammaires des langages informatiques réels sont évidemment (presque ?) toujours inambiguës : on souhaite qu'un programme (c'est-à-dire, dans la terminologie mathématique, un mot du langage) @@ -5314,6 +5482,8 @@ en \ref{trivial-example-ambiguity}). L'ambiguïté est donc une caractéristique de la \emph{grammaire} hors contexte et non du \emph{langage} algébrique qu'elle engendre. +\smallskip + Cependant, certains langages algébriques ne sont définis \emph{que} par des grammaires hors contexte ambiguës. De tels langages sont dits \defin[intrinsèquement ambigu (langage algébrique)]{intrinsèquement @@ -5353,6 +5523,8 @@ où : \end{itemize} \end{prop} +\smallskip + Donnons maintenant un exemple d'utilisation du lemme : \begin{prop}\label{example-of-pumping-lemma-for-algebraic-languages} @@ -5382,6 +5554,8 @@ peut s'avérer utile pour montrer qu'un langage n'est pas algébrique, en permettant de simplifier le langage auquel on va appliquer le lemme de pompage. +\smallskip + À titre d'exemple, montrons que le langage $L$ formé des mots sur $\{a,b,c\}$ ayant le même nombre total de $a$, de $b$ et de $c$ (autrement dit $\{w \in \{a,b,c\}^* : |w|_a = |w|_b = |w|_c\}$ où @@ -5421,6 +5595,8 @@ au sommet de la pile (jusqu'à une profondeur bornée), et une fois cette transition effectuée, décider de rajouter, retirer ou remplacer des symboles au sommet de la pile. +\medskip + {\footnotesize De façon plus formelle, un \index{automate à pile}automate à pile non déterministe est la @@ -5438,6 +5614,8 @@ mot $w$ lorsqu'il existe une suite de transitions d'un état initial avec pile vide vers un état final avec pile vide qui consomme les lettres de $w$. +\smallskip + De façon plus précise, l'automate accepte $w$ lorsqu'il existe $q_0,\ldots,q_n \in Q$ (les états traversés) et $t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ (les symboles consommés) et @@ -5458,6 +5636,8 @@ des langages acceptés.) \par} +\medskip + On peut montrer qu'il y a équivalence entre grammaires hors contexte et automates à pile non déterministes au sens où tout langage engendré par une grammaire hors contexte est le langage accepté par un automate @@ -5488,6 +5668,8 @@ hors contexte $G$ (absolument quelconque) est la suivante : s'arrêter dès qu'on dépasse la longueur $|w|$ à atteindre. \end{itemize} +\smallskip + Énonçons précisément le résultat en question : \begin{thm}\label{algebraic-languages-are-decidable} @@ -5570,6 +5752,8 @@ de reconnaître si $w \in L(G)$, et fournir une autre démonstration du théorème \ref{algebraic-languages-are-decidable}, tout en continuant à ne faire aucune hypothèse sur la grammaire hors contexte $G$. +\smallskip + Il s'agit de travailler en deux étapes : \begin{itemize} \item D'abord, trouver algorithmiquement une grammaire $G'$ et un $E @@ -5585,6 +5769,8 @@ Il s'agit de travailler en deux étapes : savoir si $S \mathrel{\Rightarrow^*} w$). \end{itemize} +\smallskip + Détaillons un peu plus chacune de ces étapes. Pour transformer la grammaire $G$ en une grammaire $G'$ sous forme @@ -5623,6 +5809,8 @@ normale de Chomsky, on effectue les transformations suivantes : L'ordre de ces transformations peut être légèrement varié, mais celui proposé ci-dessus est sans doute le meilleur. +\smallskip + Une fois la grammaire $G'$ en forme normale de Chomsky connue, lorsqu'on a un mot $w$ dont on cherche à tester s'il appartient à $L(G')$, on calcule, pour chaque facteur $u$ de $w$ (identifié par @@ -5651,6 +5839,8 @@ rechercher toutes les dérivations $Y \Rightarrow X_1 X_2 donné $v_1$ et $X_2$ a donné $v_2$. Une fois les $\Lambda(u)$ connus, tester si $w \in L(G')$ revient à tester si $S \in \Lambda(w)$. +\smallskip + L'algorithme qu'on vient de décrire (pour tester si $w \in L(G')$ une fois $G'$ sous forme normale de Chomsky) porte le nom d'\defin[Cocke-Younger-Kasami (algorithme de)]{algorithme de @@ -5680,6 +5870,8 @@ engendre) ; ces contraintes sont assez techniques et difficiles à décrire : dans la pratique, elles consistent essentiellement à essayer de fabriquer l'analyseur et à constater si l'algorithme échoue. +\smallskip + Il existe deux principales approches pour construire un analyseur pour une grammaire hors contexte (sujette à diverses contraintes supplémentaires) ; dans les deux cas, on construit une sorte @@ -5706,12 +5898,16 @@ les deux cas. De façon très simplifiée : feuilles, et qui restent encore à regrouper. \end{itemize} +\smallskip + On peut écrire un analyseur LL ou (plus difficilement) LR à la main dans un cas simple, mais en général ces analyseurs sont fabriqués par des algorithmes systématiques, implémentés dans des programmes tels que YACC ou Bison (qui produit des analyseurs LR, même si Bison peut dépasser ce cadre) ou JavaCC (qui produit des analyseurs LL). +\smallskip + L'idée générale à retenir est que les analyseurs LR sont strictement plus puissants que les analyseurs LL (ils sont capables d'analyser strictement plus de grammaires, cf. \ref{example-lr-non-ll-grammar}), @@ -5735,6 +5931,8 @@ productions $\varepsilon$ ; on peut imaginer, si on veut, qu'il s'agit d'une forme extrêmement primitive de XML où $a$ représente une balise ouvrante, $b$ une balise fermante, et $c$ une balise vide). +\medskip + L'approche la plus évidente, si on doit écrire une fonction « analyser un mot comme dérivant de $S$ dans cette grammaire » consiste à coder deux fonctions mutuellement récursives, « chercher un préfixe qui @@ -5786,6 +5984,8 @@ $S\rightarrow TS$ et $S\rightarrow c$, on va écrire : \end{itemize} \end{itemize} +\smallskip + Cette approche réussit sur cette grammaire très simple (où on peut notamment se convaincre que l'éventuel préfixe dérivant de $S$ ou de $T$ est toujours défini de façon unique). L'analyseur qu'on vient de @@ -5806,7 +6006,7 @@ C'est ici l'approche « descendante » : l'arbre se construit à partir de la racine et la pile sert à retenir les règles qu'on a commencé à reconnaître. -\smallbreak +\medbreak L'approche « ascendante » de la même grammaire serait plutôt la suivante : on parcourt le mot de gauche à droite en gardant de côté @@ -5867,6 +6067,8 @@ fastidieux que programmer un ordinateur en assembleur, donc s'il s'agit d'exhiber un algorithme, c'est probablement une mauvaise idée de l'écrire sous forme de machine de Turing). +\smallskip + Néanmoins, il est essentiel de savoir que ces formalisations existent : on peut par exemple évoquer le paradigme du $\lambda$-calcul de Church (la première formalisation rigoureuse de la @@ -5888,6 +6090,8 @@ formelles d'algorithmes, qu'on peut rassembler sous le nom commun de \defin[calculable (fonction)]{calculabilité au sens de Church-Turing}, ou « calculabilité » tout court. +\smallskip + Notamment, quasiment tous les langages de programmation informatique\footnote{C, C++, Java, Python, JavaScript, Lisp, OCaml, Haskell, Prolog, etc. Certains langages se sont même révélés @@ -5906,7 +6110,7 @@ entiers de taille arbitraire, de les comparer et de calculer les opérations arithmétiques dessus, et d'effectuer des tests et des boucles. -\medbreak +\bigbreak \thingy Il faut souligner qu'on s'intéresse uniquement à la question de savoir ce qu'un algorithme peut ou ne peut pas faire @@ -5919,6 +6123,8 @@ produits $pq$ avec $2\leq p,q\leq n-1$ et tester si l'un d'eux est égal à $n$, peu importe que cet algorithme soit absurdement inefficace. +\smallskip + De même, nos algorithmes sont capables de manipuler des entiers arbitrairement grands : ceci permet de dire, par exemple, que toute chaîne binaire peut être considérée comme un entier, peu importe le @@ -5963,9 +6169,11 @@ considérer qu'au lieu de mots on a affaire à des entiers naturels. Il va de soi que la concaténation de deux mots, la longueur d'un mot, le miroir d'un mot, sont tous calculables algorithmiquement. -On peut considérer que, dans cette partie, le terme de -\index{langage}« langage » désigne non plus une partie de $\Sigma^*$ -mais une partie de $\mathbb{N}$. +\smallskip + +Grâce au codage de Gödel, on peut considérer que, dans cette partie, +le terme de \index{langage}« langage » désigne non plus une partie de +$\Sigma^*$ mais une partie de $\mathbb{N}$. {\footnotesize (Le remplacement des mots par des entiers naturels en utilisant un codage comme on vient de le dire est assez standard en @@ -5976,7 +6184,7 @@ mais une partie de $\mathbb{N}$. d'importance ; comme $\mathbb{N}$ est un objet mathématiquement plus simple, c'est surtout pour cela qu'il est utilisé à la place.)\par} -\medbreak +\bigbreak \thingy\textbf{Terminaison des algorithmes.} Un algorithme qui effectue un calcul utile doit certainement terminer en temps fini. @@ -6015,6 +6223,8 @@ On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, et calcule (renvoie) $f(n)$. +\smallskip + On dit qu'un ensemble $A \subseteq \mathbb{N}$ (un « langage », cf. \ref{computability-all-data-are-integers}) est \defin{décidable} (ou \index{calculable (langage)|see{décidable}}« calculable » ou @@ -6026,6 +6236,8 @@ $n\in\mathbb{N}$, termine toujours en temps fini, et renvoie « oui » ($1$) si $n\in A$, « non » ($0$) si $n\not\in A$ (on dira que l'algorithme « décide » $A$). +\smallskip + On dit qu'une fonction partielle $f\colon\mathbb{N}\dasharrow\mathbb{N}$ (c'est-à-dire une fonction définie sur une partie de $\mathbb{N}$, appelé ensemble de définition @@ -6041,10 +6253,12 @@ On utilisera la notation $f(n)\downarrow$ pour signifier le fait que la fonction calculable partielle $f$ est définie en $n$, c'est-à-dire, que l'algorithme en question termine. +\smallskip + On dit qu'un ensemble $A \subseteq \mathbb{N}$ est -\defin{semi-décidable} (ou \index{semi-calculable - (langage)|see{semi-décidable}}« semi-calculable » ou -\index{semi-récursif (langage)|see{semi-décidable}}« semi-récursif ») +\defin{semi-décidable} (ou +\index{semi-calculable|see{semi-décidable}}« semi-calculable » ou +\index{semi-récursif|see{semi-décidable}}« semi-récursif ») lorsque la fonction partielle $\mathbb{N}\dasharrow\mathbb{N}$ définie exactement sur $A$ et y valant $1$, est calculable partielle. Autrement dit : lorsqu'il existe un algorithme qui prend en entrée @@ -6056,6 +6270,8 @@ et renvoie « oui » ($1$) dans ce cas\footnote{En fait, la valeur « semi-décide » $A$). \end{defn} +\smallskip + On s'est limité ici à des fonctions d'une seule variable (entière), mais il n'y a pas de difficulté à étendre ces notions à plusieurs variables, et de parler de fonction calculable $\mathbb{N}^k \to @@ -6221,6 +6437,8 @@ sont pas importants\footnote{Par exemple, ceux qui aiment le langage ce programme est valable (remplacer Java par tout autre langage préféré).}. +\medskip + Un point crucial dans cette numérotation des algorithmes est l'existence d'une \defin[universelle (machine)]{machine universelle}, c'est-à-dire d'un algorithme $U$ qui prend en entrée un entier $e$ @@ -6229,6 +6447,8 @@ que $T$ sur l'entrée $n$ (i.e., $U$ termine sur les entrées $e$ et $n$ si et seulement si $T$ termine sur l'entrée $n$, et, dans ce cas, renvoie la même valeur). +\smallskip + Informatiquement, ceci représente le fait que les programmes informatiques sont eux-mêmes représentables informatiquement : dans un langage de programmation Turing-complet, on peut écrire un @@ -6248,6 +6468,8 @@ qui, donnée une description (formelle !) d'un algorithme et une entrée à laquelle l'appliquer, effectue l'exécution de l'algorithme fourni sur l'entrée fournie. +\smallskip + On ne peut pas démontrer ce résultat ici faute d'une description rigoureuse d'un modèle de calcul précis, mais il n'a rien de conceptuellement difficile (même s'il peut être fastidieux à écrire @@ -6283,12 +6505,14 @@ programmation demande un minimum d'efforts). précisément comment le codage standard est fait pour une formalisation de la calculabilité).\par} +\smallskip + La machine universelle n'a rien de « magique » : elle se contente de suivre les instructions de l'algorithme $T$ qu'on lui fournit, et termine si et seulement si $T$ termine. Peut-on savoir à l'avance si $T$ terminera ? C'est le fameux « problème de l'arrêt ». -\smallbreak +\medbreak Intuitivement, le « problème de l'arrêt » est la question « l'algorithme suivant termine-t-il sur l'entrée suivante » ? @@ -6390,6 +6614,8 @@ semi-décidable, son complémentaire ne l'est pas. $h(e, n)$ la fonction qui n'est pas définie si $\varphi_e(n)$ l'est et qui vaut $42$ si $\varphi_e(n)$ n'est pas définie.\par} +\medbreak + La non-décidabilité du problème de l'arrêt est un résultat fondamental, car très souvent les résultats de non-décidabilité soit sont démontrés sur un modèle semblable, soit s'y ramènent @@ -6439,7 +6665,7 @@ construire un algorithme résolvant le problème de l'arrêt. i\leq n\}$ domine asymptotiquement n'importe quelle fonction calculable mais c'est un peu plus difficile.\par} -\medbreak +\bigbreak {\footnotesize\thingy\textbf{Application à la logique :} Sans rentrer dans les détails de ce que signifie un « système formel », on peut |