summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-07 21:25:30 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-11-07 21:25:30 (GMT)
commit11c2170709dde97c596e463cd8f2f7d06b6f4e61 (patch)
tree77321045cf24782c7a0eb5ee57e601b29d6b7c88 /notes-inf105.tex
parentc4d98bd981a3a204b495bf3071f4b5728814a4b5 (diff)
downloadinf105-11c2170709dde97c596e463cd8f2f7d06b6f4e61.zip
inf105-11c2170709dde97c596e463cd8f2f7d06b6f4e61.tar.gz
inf105-11c2170709dde97c596e463cd8f2f7d06b6f4e61.tar.bz2
Corrections suggested by Jacques.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex16
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