summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex105
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