From c7ec3f78b0bd5d10f0e9bc517de0d8408dc0dfab Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 7 Jan 2019 14:35:28 +0100
Subject: Various improvements to index.
---
notes-inf105.tex | 56 +++++++++++++++++++++++++++++++-------------------------
1 file changed, 31 insertions(+), 25 deletions(-)
diff --git a/notes-inf105.tex b/notes-inf105.tex
index ef982a0..8dd9af9 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -611,7 +611,7 @@ une chaîne de caractères et renvoyant un booléen.
\thingy\label{union-and-intersection-of-languages} Si $L_1$ et $L_2$
sont deux langages sur un même alphabet $\Sigma$ (autrement dit,
$L_1,L_2 \subseteq \Sigma^*$), on peut former les langages
-\defin[union (de langages)]{union} $L_1\cup L_2$ et
+\index{réunion (de langages)|see{union}}\defin[union (de langages)]{union} $L_1\cup L_2$ et
\defin[intersection (de langages)]{intersection} $L_1\cap L_2$ qui
sont simplement les opérations ensemblistes usuelles (entre parties
de $\Sigma^*$).
@@ -2455,7 +2455,7 @@ traite des opérations rationnelles.
\begin{prop}\label{dfa-complement}
Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
-le complémentaire $\Sigma^*\setminus L$ de $L$ est reconnaissable ; de
+le \index{complémentaire (langage)}complémentaire $\Sigma^*\setminus L$ de $L$ est reconnaissable ; de
plus, un DFA reconnaissant l'un se déduit algorithmiquement d'un DFA
reconnaissant l'autre.
\end{prop}
@@ -2484,7 +2484,8 @@ même chose que l'inexistence d'un chemin aboutissant à un état final.)
\begin{prop}\label{dfa-union-and-intersection}
Si $L_1,L_2$ sont des langages reconnaissables (sur un même
-alphabet $\Sigma$), alors la réunion $L_1\cup L_2$ et l'intersection
+alphabet $\Sigma$), alors la \index{union (de langages)}réunion
+$L_1\cup L_2$ et \index{intersection (de langages)}l'intersection
$L_1\cap L_2$ sont reconnaissables ; de plus, un DFA reconnaissant
l'un comme l'autre se déduit algorithmiquement de DFA reconnaissant
$L_1$ et $L_2$.
@@ -2665,9 +2666,9 @@ Donnons maintenant une autre preuve de ce fait, à base de NFA :
\begin{prop}\label{nfa-union}
Si $L_1,L_2$ sont des langages reconnaissables (sur un même
-alphabet $\Sigma$), alors la réunion $L_1 \cup L_2$ est
-reconnaissable ; de plus, un NFA la reconnaissant se déduit
-algorithmiquement de NFA reconnaissant $L_1$ et $L_2$.
+alphabet $\Sigma$), alors la \index{union (de langages)}réunion $L_1
+\cup L_2$ est reconnaissable ; de plus, un NFA la reconnaissant se
+déduit algorithmiquement de NFA reconnaissant $L_1$ et $L_2$.
\end{prop}
\begin{proof}
Par hypothèse, il existe des NFA reconnaissant $L_1$ et $L_2$ :
@@ -2770,9 +2771,10 @@ bien $L(A') = L_1 \cup L_2$.
\begin{prop}\label{nfa-concatenation}
Si $L_1,L_2$ sont des langages reconnaissables (sur un même
-alphabet $\Sigma$), alors la concaténation $L_1 L_2$ est
-reconnaissable ; de plus, un NFA la reconnaissant se déduit
-algorithmiquement de NFA reconnaissant $L_1$ et $L_2$.
+alphabet $\Sigma$), alors la \index{concaténation (de
+ langages)}concaténation $L_1 L_2$ est reconnaissable ; de plus, un
+NFA la reconnaissant se déduit algorithmiquement de NFA reconnaissant
+$L_1$ et $L_2$.
\end{prop}
\begin{proof}
Par hypothèse, il existe des NFA reconnaissant $L_1$ et $L_2$ :
@@ -2872,8 +2874,9 @@ final dans $A_1$ suivi d'un chemin de $q_2$ à un état final dans $A_2$
\begin{prop}\label{nfa-star}
Si $L$ est un langage reconnaissable (sur un alphabet $\Sigma$), alors
-l'étoile de Kleene $L^*$ est reconnaissable ; de plus, un NFA la
-reconnaissant se déduit algorithmiquement de NFA reconnaissant $L$.
+\index{étoile de Kleene}l'étoile de Kleene $L^*$ est reconnaissable ;
+de plus, un NFA la reconnaissant se déduit algorithmiquement de NFA
+reconnaissant $L$.
\end{prop}
\begin{proof}
Par hypothèse, il existe un NFA reconnaissant $L$ :
@@ -4567,7 +4570,8 @@ des lettres d'un alphabet $\Sigma$ abstrait.
\subsection{Définition, notations et premier exemple}\label{subsection-context-free-grammars}
-\thingy\label{definition-context-free-grammar} Une \defin{grammaire
+\thingy\label{definition-context-free-grammar} Une \index{hors
+ contexte (grammaire)|see{grammaire hors contexte}}\defin{grammaire
hors contexte} (on dit parfois aussi « sans contexte » ; en anglais,
« context-free grammar » ou \index{CFG|see{grammaire hors
contexte}}« CFG » ; ou encore grammaire de \textbf{type 2}) sur un
@@ -4857,20 +4861,21 @@ Les grammaires régulières sont également appelées grammaires de
\begin{prop}\label{cfg-union-concatenation-and-star}
Si $L_1,L_2$ sont des langages algébriques (sur un même
-alphabet $\Sigma$), alors la réunion $L_1 \cup L_2$ est algébrique ;
-de plus, une grammaire hors contexte l'engendrant se déduit
-algorithmiquement de grammaires hors contexte engendrant $L_1$
-et $L_2$.
+alphabet $\Sigma$), alors la \index{union (de langages)}réunion $L_1
+\cup L_2$ est algébrique ; de plus, une grammaire hors contexte
+l'engendrant se déduit algorithmiquement de grammaires hors contexte
+engendrant $L_1$ et $L_2$.
Si $L_1,L_2$ sont des langages algébriques (sur un même
-alphabet $\Sigma$), alors la concaténation $L_1 L_2$ est algébrique ;
-de plus, une grammaire hors contexte l'engendrant se déduit
-algorithmiquement de grammaires hors contexte engendrant $L_1$
-et $L_2$.
-
-Si $L$ est un langage algébrique, alors l'étoile de Kleene $L^*$ est
-algébrique ; de plus, une grammaire hors contexte l'engendrant se
-déduit algorithmiquement d'une grammaire hors contexte engendrant $L$.
+alphabet $\Sigma$), alors la \index{concaténation (de
+ langages)}concaténation $L_1 L_2$ est algébrique ; de plus, une
+grammaire hors contexte l'engendrant se déduit algorithmiquement de
+grammaires hors contexte engendrant $L_1$ et $L_2$.
+
+Si $L$ est un langage algébrique, alors \index{étoile de
+ Kleene}l'étoile de Kleene $L^*$ est algébrique ; de plus, une
+grammaire hors contexte l'engendrant se déduit algorithmiquement d'une
+grammaire hors contexte engendrant $L$.
\end{prop}
\begin{proof}
Pour la réunion : supposons que $G_1$ et $G_2$ engendrent $L_1$ et
@@ -6174,7 +6179,8 @@ alphabet fini), en calculabilité, il est possible, dès que cela est
commode, de remplacer ceux-ci par des entiers naturels.
Il suffit pour cela de choisir un « codage », parfois appelé
-\defin{codage de Gödel} permettant de représenter un élément de
+\index{Gödel (codage de)|see{codage de Gödel}}\defin{codage de Gödel}
+permettant de représenter un élément de
$\Sigma^*$ par un entier naturel : la chose importante est que la
conversion d'un mot en entier ou d'un entier en mot soit calculable
par un algorithme (même très inefficace), si bien que toute
--
cgit v1.2.3