diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 818b58b..c25f409 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1014,7 +1014,7 @@ suivante : $(a|b){*} \equiv (écrite avec les conventions de \ref{convention-on-writing-regexps}) ; la question d'arriver à trouver un système d'axiomes qui permet de déduire toutes les équivalences entre expressions rationnelles est un -problème délicat. +problème délicat (il n'y en a notamment pas qui soit fini). \par} @@ -1123,7 +1123,7 @@ qu'avec des caractères individuels ; en contrepartie, on peut écrire des intervalles comme « \texttt{[a-z]} » qui désigne un caractère quelconque entre \texttt{a} et \texttt{z} dans l'ordre ASCII/Unicode\footnote{...ou parfois l'ordre de tri défini par la - locale en cours : c'est malheureusement une source supplémentaire de + « locale » en cours : c'est malheureusement une source supplémentaire de confusion et de bugs.}, ou bien des négations, comme « \texttt{[\char"5Ea-z]} » qui désigne un caractère qui \emph{n'est pas} entre \texttt{a} et \texttt{z}) ou @@ -1447,7 +1447,7 @@ définitivement et qui constitue le seul état acceptant. %%% end example2 %%% \end{center} -Cette description rend claire le fait que l'automate en question +Cette description rend clair le fait que l'automate en question accepte exactement les mots contenant un $a$ suivi, pas forcément immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un sous-mot (cf. \ref{definition-subword}). Ce langage est donc @@ -1464,7 +1464,7 @@ l'automate arrive (en partant de l'état initial et en consommant un certain mot). Dans le cas contraire, l'état est dit \textbf{inaccessible}. Il est évident qu'ajouter ou supprimer (ou modifier) les états inaccessibles dans un DFA ne change rien au -langage reconnu (on obtient des langages équivalents). +langage reconnu (on obtient des automates équivalents). Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible (l'automate est donc équivalent à celui représenté @@ -1889,7 +1889,7 @@ mais cette fois-ci, le coût algorithmique de la transformation peut \begin{prop}\label{determinization-of-nfa} Soit $A = (Q,I,F,\delta)$ un NFA sur un alphabet $\Sigma$. Alors il -existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même +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 algorithmiquement de $A$ avec une augmentation au plus exponentielle @@ -1900,7 +1900,7 @@ On définit $Q' = \mathscr{P}(Q) = \{\mathbf{q} \subseteq Q\}$ l'\emph{ensemble des parties} de $Q$ : c'est ce qui servira d'ensemble d'états du DFA $A'$ qu'on construit (i.e., un état de $A'$ est un ensemble d'états de $A$ — intuitivement, c'est l'ensemble des états -dans lesquels on se trouve simultanément). On pose $q'_0 = I$ (l'état +dans lesquels on se trouve simultanément). On pose $\textbf{q}'_0 = I$ (l'état initial de $A'$ sera l'ensemble de tous les états initiaux de $A$, vu comme un élément de $Q'$) ; et on pose $F' = \{\mathbf{q}\subseteq Q :\penalty-100 \mathbf{q}\cap F \neq\varnothing\}$ : les états finaux @@ -2864,8 +2864,8 @@ renvoie à \ref{glushkov-construction} ci-dessous (ou à algorithmique plus précise. Pour décider si un mot $w$ vérifie une expression rationnelle $r$, on -commencer par transformer cette expression rationnelle en NFA comme on -vient de l'expliquer (c'est-à-dire à construrie un NFA $A_r$ +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 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 |