diff options
| -rw-r--r-- | notes-inf105.tex | 56 |
1 files 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 |