diff options
| -rw-r--r-- | notes-inf105.tex | 105 |
1 files changed, 53 insertions, 52 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index c25f409..7d7b576 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -885,28 +885,28 @@ caractères \emph{n'appartenant pas} à l'alphabet $\Sigma$, appelés manière dont est formée l'expression rationnelle. On définit simultanément la notion d'expression rationnelle $r$ et de \defin[dénoté (langage)]{langage dénoté} (ou \textbf{désigné} ou -simplement \textbf{défini}) $L_r$ par l'expression $r$, de la manière -suivante : +simplement \textbf{défini}) $L(r)$ (ou $L_r$) par l'expression $r$, de +la manière suivante : \begin{itemize} \item $\bot$ est une expression rationnelle et son langage dénoté - est $L_\bot := \varnothing$, + est $L(\bot) := \varnothing$, \item $\underline{\varepsilon}$ est une expression rationnelle et son - langage dénoté est $L_{\underline{\varepsilon}} := + langage dénoté est $L(\underline{\varepsilon}) := \{\varepsilon\}$, \item si $x\in\Sigma$ est une lettre de l'alphabet $\Sigma$, alors le mot $x$ est une expression rationnelle et son langage dénoté - est $L_x := \{x\}$, + est $L(x) := \{x\}$, \item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 = - L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénotés correspondants, + L(r_1)$ et $L_2 = L(r_2)$ les langages dénotés correspondants, alors $r_1 r_2$ est une expression rationnelle et son langage - dénoté est $L_{r_1 r_2} := L_1 L_2$, + dénoté est $L(r_1 r_2) := L_1 L_2$, \item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 = - L_{r_1}$ et $L_2 = L_{r_2}$ les langages dénotés correspondants, + L(r_1)$ et $L_2 = L(r_2)$ les langages dénotés correspondants, alors $(r_1|r_2)$ est une expression rationnelle\footnote{Certains préfèrent la notation $r_1+r_2$ ici, cf. \ref{regexp-notation-variations} pour une discussion.} et son - langage dénoté est $L_{(r_1|r_2)} := L_1\cup L_2$, -\item si $r$ est une expression rationnelle et $L = L_r$ les langage + langage dénoté est $L((r_1|r_2)) := L_1\cup L_2$, +\item si $r$ est une expression rationnelle et $L = L(r)$ les langage dénoté correspondant, alors $(r){*}$ est une expression rationnelle\footnote{Notons que certains auteurs préfèrent mettre le $*$ en exposant ici, c'est-à-dire noter $(r)^*$ (comme nous @@ -920,7 +920,7 @@ suivante : deux notations $X^*$ et $X{*}$ auraient tous les deux un sens et que ces sens diffèrent ! On peut donc ignorer purement et simplement la question de savoir si oui ou non l'étoile est en - exposant.} et son langage dénoté est $L_{(r){*}} := L^*$. + exposant.} et son langage dénoté est $L((r){*}) := L^*$. \end{itemize} Un langage rationnel est par construction la même chose qu'un langage @@ -958,7 +958,7 @@ $\Sigma = \{a,b,c,d\}$ : \thingy On dira qu'un mot $w$ \defin[vérifier (une expression rationnelle)]{vérifie} une expression rationnelle $r$ lorsque ce mot -appartient au langage qu'elle dénote (i.e., $w \in L_r$). Par +appartient au langage qu'elle dénote (i.e., $w \in L(r)$). Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$. \thingy Deux expressions rationnelles $r_1,r_2$ sont dites @@ -1407,18 +1407,19 @@ Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ $\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il \textbf{rejette} le mot $w$. -\thingy\label{definition-recognizable-language} L'ensemble $L_A$ des -mots acceptés par l'automate $A$ s'appelle \textbf{langage accepté}, -ou \textbf{reconnu}, ou \textbf{défini}, par l'automate $A$. +\thingy\label{definition-recognizable-language} L'ensemble $L(A)$ +(ou $L_A$) des mots acceptés par l'automate $A$ s'appelle +\textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par +l'automate $A$. 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 $L(A)$ accepté par un DFA $A$ s'appelle \defin[reconnaissable (langage)]{reconnaissable} (sous-entendu : par automate déterministe fini). 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'}$. +i.e., $L(A) = L(A')$. \thingy\label{discussion-example2} Donnons un exemple : l'automate fini ci-dessous sur $\Sigma := \{a,b,c\}$ a trois états, $Q = @@ -1587,7 +1588,7 @@ 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. -Le langage accepté $L_A$ et l'équivalence de deux automates sont +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}). @@ -1623,7 +1624,7 @@ $c{*}ac{*}bc{*}$.) Soit $A = (Q,q_0,F,\delta)$ un DFAi sur un alphabet $\Sigma$. Alors il existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît -le même langage $L_{A'} = L_A$. De plus, $A'$ se déduit +le même langage $L(A') = L(A)$. De plus, $A'$ se déduit algorithmiquement de $A$ en ajoutant au plus un état « puits » à $A$ : on a $\#Q' \leq \#Q + 1$. \end{prop} @@ -1843,7 +1844,7 @@ de $w$) : 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 +langage accepté $L(A)$ et l'équivalence de deux automates sont définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). @@ -1891,7 +1892,7 @@ mais cette fois-ci, le coût algorithmique de la transformation peut Soit $A = (Q,I,F,\delta)$ un NFA sur un alphabet $\Sigma$. Alors il existe un DFA $A' = (Q',\textbf{q}'_0,F',\delta')$ (sur le même alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît -le même langage $L_{A'} = L_A$. De plus, $A'$ se déduit +le même langage $L(A') = L(A)$. De plus, $A'$ se déduit algorithmiquement de $A$ avec une augmentation au plus exponentielle du nombre d'états : $\#Q' \leq 2^{\#Q}$. \end{prop} @@ -1920,9 +1921,9 @@ transitions de $A$ étiquetées par les lettres de $w$. En particulier, $\delta^{\prime*}(I,w)$ est l'ensemble de tous les états de $A$ auxquels on peut accéder depuis un état initial de $A$ par une suite de transitions de $A$ étiquetées par les lettres de $w$ : le mot $w$ -appartient à $L_A$ si et seulement si cet ensemble contient un élément +appartient à $L(A)$ si et seulement si cet ensemble contient un élément de $F$, ce qui par définition de $F'$ signifie exactement -$\delta^{\prime*}(I,w) \in F'$. On a bien prouvé $L_{A'} = L_A$. +$\delta^{\prime*}(I,w) \in F'$. On a bien prouvé $L(A') = L(A)$. Enfin, $\#Q' = \#\mathscr{P}(Q) = 2^{\#Q}$ (car une partie de $Q$ peut se voir à travers sa fonction indicatrice, qui est une fonction $Q \to @@ -2110,7 +2111,7 @@ $(q_{i-1},t_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w 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 +langage accepté $L(A)$ et l'équivalence de deux automates sont définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). @@ -2165,7 +2166,7 @@ Soit $A = (Q,I,F,\delta)$ un εNFA sur un alphabet $\Sigma$. Alors il existe un NFA $A^\S = (Q,I^\S,F^\S,\delta^\S)$ (sur le même alphabet $\Sigma$) ayant le même ensemble d'états $Q$ que $A$ et qui soit équivalent à $A$ au sens où il reconnaît le même langage -$L_{A^\S} = L_A$. De plus, $A^\S$ se déduit algorithmiquement de $A$. +$L(A^\S) = L(A)$. De plus, $A^\S$ se déduit algorithmiquement de $A$. \end{prop} \begin{proof} On pose $I^\S = I$ (mêmes états initiaux). L'idée est maintenant de @@ -2309,7 +2310,7 @@ simplifie la description). \thingy On rappelle qu'on a défini un langage \index{reconnaissable (langage)}reconnaissable comme un langage $L$ pour lequel il existe -un DFA $A$ tel que $L = L_A$. D'après \ref{completion-of-dfai}, +un DFA $A$ tel que $L = L(A)$. D'après \ref{completion-of-dfai}, \ref{determinization-of-nfa} et \ref{removal-of-epsilon-transitions}, on peut remplacer « DFA » dans cette définition par « DFAi », « NFA » ou « εNFA » sans changer la définition. @@ -2329,16 +2330,16 @@ reconnaissant l'autre. \end{prop} \begin{proof} Par hypothèse, il existe un DFA (complet !) $A = (Q,q_0,F,\delta)$ tel -que $L = L_A$. Considérons le DFA $A'$ défini par l'ensemble d'états +que $L = L(A)$. Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = Q$, l'état initial $q'_0 = q_0$, la fonction de transition $\delta' = \delta$ et pour seul changement l'ensemble d'états finaux $F' = Q \setminus F$ complémentaire de $F$. -Pour $w \in \Sigma^*$, on a $w \in L_{A'}$ si et seulement si +Pour $w \in \Sigma^*$, on a $w \in L(A')$ si et seulement si $\delta^{\prime*}(q_0,w) \in F'$, c'est-à-dire $\delta^*(q_0,w) \in F'$ (puisque $\delta' = \delta$), c'est-à-dire $\delta^*(q_0,w) \not\in F$ (par définition du complémentaire), c'est-à-dire $w \not\in -L_A$. Ceci montre bien que $L_{A'}$ est le complémentaire de $L_A$. +L(A)$. Ceci montre bien que $L(A')$ est le complémentaire de $L(A)$. \end{proof} \thingy Cette démonstration a utilisé la caractérisation des langages @@ -2360,8 +2361,8 @@ $L_1$ et $L_2$. \begin{proof} Traitons le cas de l'intersection. Par hypothèse, il existe des DFA (complets !) $A_1 = (Q_1,q_{0,1},F_1,\delta_1)$ et $A_2 = -(Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 = -L_{A_2}$. Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = +(Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L(A_1)$ et $L_2 = +L(A_2)$. Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = Q_1 \times Q_2$ (c'est-à-dire l'ensemble des couples formés d'un état de $A_1$ et d'un état de $A_2$), l'état initial $q'_0 = (q_{0,1},q_{0,2})$, la fonction de transition $\delta' \colon @@ -2374,7 +2375,7 @@ ailleurs, si $w\in \Sigma^*$, on a $\delta^{\prime*}(q_0',w) = (\delta_1^*(q_{0,1},w), \delta_2^*(q_{0,2},w))$, et par ce qui vient d'être dit, ceci appartient à $F'$ si et seulement $\delta_1^*(q_{0,1},w) \in F_1$ et $\delta_2^*(q_{0,2},w) \in F_2$. -On voit donc qu'un mot $w$ appartient à $L_{A'}$ si et seulement il +On voit donc qu'un mot $w$ appartient à $L(A')$ si et seulement il appartient à la fois à $L_1$ et à $L_2$, ce qu'il fallait démontrer. Pour la réunion, on peut invoquer le fait que la réunion est le @@ -2420,15 +2421,15 @@ $A^{\mathsf{R}}$ de $A$. \begin{proof} Par hypothèse, il existe un NFA ou un εNFA $A = (Q,I,F,\delta)$ tel -que $L = L_A$. Considérons l'automate $A^{\mathsf{R}}$ de même type +que $L = L(A)$. Considérons l'automate $A^{\mathsf{R}}$ de même type défini par l'ensemble d'états $Q^{\mathsf{R}} = Q$ et inversant toutes les flèches de $A$, c'est-à-dire $I^{\mathsf{R}} = F$ et $F^{\mathsf{R}} = I$ et $(q,t,q') \in \delta^{\mathsf{R}}$ si et seulement si $(q',t,q) \in \delta$. Un chemin existe dans $A^{\mathsf{R}}$ si et seulement si le même chemin inversé existe -dans $A$, ce qui montre qu'un mot appartient à $L_{A^{\mathsf{R}}}$ si -et seulement si son miroir appartient à $L_A$. On a donc bien -$L_{A^{\mathsf{R}}}=L^{\mathsf{R}}$, langage miroir de $L$. +dans $A$, ce qui montre qu'un mot appartient à $L(A^{\mathsf{R}})$ si +et seulement si son miroir appartient à $L(A)$. On a donc bien +$L(A^{\mathsf{R}})=L^{\mathsf{R}}$, langage miroir de $L$. \end{proof} \thingy Alors que les constructions du complémentaire et de @@ -2539,7 +2540,7 @@ d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils sont \emph{standards} en ce sens qu'ils ont un unique état initial qui n'est la cible d'aucune transition. Disons que $A_1 = (Q_1,\{q_1\},F_1,\delta_1)$ et $A_2 = (Q_2,\{q_2\},F_2,\delta_2)$ sont -des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. +des NFA standards tels que $L_1 = L(A_1)$ et $L_2 = L(A_2)$. L'automate $A'$ s'obtient réunissant $A_1$ et $A_2$ mais en « fusionnant » les états initiaux $q_1$ et $q_2$ de $A_1$ et $A_2$ en @@ -2629,7 +2630,7 @@ vient d'être dit.) Il est alors clair qu'un chemin de l'état initial à un état final dans cet automate $A'$ consiste soit en un chemin d'un état initial à un état final dans $A_1$ soit en un tel chemin dans $A_2$. On a donc -bien $L_{A'} = L_1 \cup L_2$. +bien $L(A') = L_1 \cup L_2$. \end{proof} \begin{prop}\label{nfa-concatenation} @@ -2644,7 +2645,7 @@ d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils sont \emph{standards} en ce sens qu'ils ont un unique état initial qui n'est la cible d'aucune transition. Disons que $A_1 = (Q_1,\{q_1\},F_1,\delta_1)$ et $A_2 = (Q_2,\{q_2\},F_2,\delta_2)$ sont -des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. +des NFA standards tels que $L_1 = L(A_1)$ et $L_2 = L(A_2)$. L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant @@ -2731,7 +2732,7 @@ dit.) Il est alors clair qu'un chemin de l'état initial $q_1$ à un état final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état final dans $A_1$ suivi d'un chemin de $q_2$ à un état final dans $A_2$ -(moins $q_2$ lui-même). On a donc bien $L_{A'} = L_1 L_2$. +(moins $q_2$ lui-même). On a donc bien $L(A') = L_1 L_2$. \end{proof} \begin{prop}\label{nfa-star} @@ -2744,7 +2745,7 @@ Par hypothèse, il existe un NFA reconnaissant $L$ : d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils est \emph{standard} en ce sens qu'il a un unique état initial qui n'est la cible d'aucune transition. Disons que $A = (Q,\{q_0\},F,\delta)$ est -un NFA standard tel que $L = L_A$. +un NFA standard tel que $L = L(A)$. L'automate $A'$ s'obtient en ajoutant à $A$, pour chaque transition sortant de $q_0$, une transition identiquement étiquetée, et de même @@ -2805,7 +2806,7 @@ dit.) Il est alors clair qu'un chemin de l'état initial $q_0$ à un état final dans cet automate $A'$ consiste en un nombre quelconque (éventuellement nul) de chemins de l'état initial à un état final -dans $A$. On a donc bien $L_{A'} = L^*$. +dans $A$. On a donc bien $L(A') = L^*$. \end{proof} \thingy\label{trivial-standard-automata} Il sera utile de fixer @@ -2847,7 +2848,7 @@ le dénotant. En particulier, il existe un algorithme qui, donnée une expression rationnelle $r$ (sur un alphabet $\Sigma$) et un mot $w \in \Sigma^*$, -décide si $w\in L_r$, c'est-à-dire si $w$ vérifie $r$. (Autrement +décide si $w\in L(r)$, c'est-à-dire si $w$ vérifie $r$. (Autrement dit, les langages algébriques sont \emph{décidables} au sens de \ref{definition-computable-function-or-set}.) \end{cor} @@ -2866,7 +2867,7 @@ algorithmique plus précise. Pour décider si un mot $w$ vérifie une expression rationnelle $r$, on commence par transformer cette expression rationnelle en NFA comme on vient de l'expliquer (c'est-à-dire à construire un NFA $A_r$ -reconnaissant le langage $L_r$ dénoté par $r$), puis on déterminise +reconnaissant le langage $L(r)$ dénoté par $r$), puis on déterminise cet automate (cf. \ref{determinization-of-nfa}), après quoi il est facile de tester si le DFA résultant de la déterministaion accepte le mot $w$ considéré (il suffit de suivre l'unique chemin dans l'automate @@ -2884,7 +2885,7 @@ les constructions décrites dans les démonstrations de \ref{nfa-union}, 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}, -qui reconnaît le langage $L_r$ dénoté par $r$, de la manière suivante +qui reconnaît le langage $L(r)$ dénoté par $r$, de la manière suivante (par induction sur la complexité de l'expression rationnelle telle que définie en \ref{regular-expressions}) : \begin{itemize} @@ -2905,7 +2906,7 @@ définie en \ref{regular-expressions}) : 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 +\item c'est un NFA reconnaissant le langage $L(r)$ dénoté par l'expression rationnelle $r$ dont on est parti, \item il est standard au sens de \ref{standard-automaton-lemma}, c'est-à-dire qu'il possède un unique état initial auquel n'aboutit @@ -3051,7 +3052,7 @@ construction, plus transparente mais moins efficace : la rationnelle $r$ un automate reconnaissant le langage qu'elle dénote. Elle possède pour sa part les propriétés suivantes : \begin{itemize} -\item c'est un εNFA reconnaissant le langage $L_r$ dénoté par +\item c'est un εNFA reconnaissant le langage $L(r)$ dénoté par l'expression rationnelle $r$ dont on est parti, \item il possède un unique état initial auquel n'aboutit aucune transition, et un unique état final duquel ne part aucune @@ -3317,7 +3318,7 @@ $\delta$ des transitions permises soit fini car l'ensemble $Q \times lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $r_1,\ldots,r_n \in \mathrm{regexp}(\Sigma)$ tels que $q_0 = q$ et $q_n = q'$ et $(q_{i-1},r_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w -\in L_{r_1\cdots r_n}$. +\in L(r_1\cdots r_n)$. Concrètement, $(q,w,q') \in \delta^*$ signifie que le RNFA peut passer de l'état $q$ à l'état $q'$ en effectuant des transitions @@ -3325,11 +3326,11 @@ passer de l'état $q$ à l'état $q'$ en effectuant des transitions \mathrm{regexp}(\Sigma)$) et en consommant le mot $w$ au sens où ce dernier se décompose comme concaténation d'autant de facteurs que de transitions ($w = v_1\cdots v_n$), chacun vérifiant l'expression -rationnelle qui étiquette la transition (soit $v_i \in L_{r_i}$). +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 +langage accepté $L(A)$ et l'équivalence de deux automates sont définis de façon analogue aux DFA (cf. \ref{definition-recognizable-language}). @@ -3368,7 +3369,7 @@ ramener aux automates précédemment définis : Soit $A = (Q,I,F,\delta)$ un RNFA sur un alphabet $\Sigma$. Alors il existe un εNFA $A' = (Q',I',F',\delta')$ (sur le même alphabet $\Sigma$) et qui soit équivalent à $A$ au sens où il -reconnaît le même langage $L_{A'} = L_A$. De plus, $A'$ se déduit +reconnaît le même langage $L(A') = L(A)$. De plus, $A'$ se déduit algorithmiquement de $A$. \end{prop} \begin{proof} @@ -3422,7 +3423,7 @@ expressions rationnelles ! Soit $A = (Q,I,F,\delta)$ un RNFA (ou, en particulier, un NFA ou DFA(i)) sur un alphabet $\Sigma$. Alors il existe une expression rationnelle $r$ sur $\Sigma$ qui dénote le langage reconnu par $A$, -soit $L_r = L_A$. De plus, $r$ se déduit algorithmiquement de $A$. +soit $L(r) = L(A)$. De plus, $r$ se déduit algorithmiquement de $A$. \end{prop} \begin{proof} On a expliqué qu'on pouvait considérer une expression rationnelle |