summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-14 11:54:22 +0100
committerDavid A. Madore <david+git@madore.org>2017-11-14 11:54:22 +0100
commitdf54f750dc8b17fc334a7d169e0d6aaef326b31a (patch)
treebb63ab0c2b6e61243b5f96ecfb84a9b668de5502
parente6ef0c54de9febf72883b94bba99064ce18f8740 (diff)
downloadinf105-df54f750dc8b17fc334a7d169e0d6aaef326b31a.tar.gz
inf105-df54f750dc8b17fc334a7d169e0d6aaef326b31a.tar.bz2
inf105-df54f750dc8b17fc334a7d169e0d6aaef326b31a.zip
Plenty more typos (thanks, Hélène S.).
-rw-r--r--notes-inf105.tex22
1 files changed, 11 insertions, 11 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 3c5b549..158db95 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2329,7 +2329,7 @@ démonstration de cette proposition, et en supprimant tous les états
non-initiaux de $A^\S$ auxquels n'aboutissent dans $A$ que des
ε-transitions (ces états sont devenus inaccessibles dans $A^\S$).
Algorithmiquement, il s'agit donc, pour chaque état $q\in Q$ et chaque
-$q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer une transition
+$q^\sharp$ dans la ε-fermeture $C(q)$ de $q$, de créer une transition
$q\to q'$ étiquetée par $x$ dans $A^\S$ pour chaque transition
$q^\sharp\to q'$ étiquetée par $x$ dans $A$.
@@ -2535,7 +2535,7 @@ et finaux).
L'automate ainsi construit en inversant toutes les flèches d'un
automate $A$ (la définition précise est donnée dans la démonstration
qui suit) et qui reconnaît le langage miroir de celui reconnu par $A$
-peut s'appeller automate \defin[transposé (automate)]{transposé}
+peut s'appeler automate \defin[transposé (automate)]{transposé}
$A^{\mathsf{R}}$ de $A$.
\begin{proof}
@@ -2990,7 +2990,7 @@ 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
+facile de tester si le DFA résultant de la déterminisation accepte le
mot $w$ considéré (il suffit de suivre l'unique chemin dans l'automate
partant de l'état initial et étiqueté par $w$, et de voir si l'état
auquel il aboutit est final).
@@ -3060,7 +3060,7 @@ Ces observations sont utiles pour détecter des erreurs lors de la
construction de l'automate.
\thingy À titre d'exemple pour illustrer la construction de Glushkov,
-construsions l'automate qu'elle associe à l'expression rationnelle
+construisons l'automate qu'elle associe à l'expression rationnelle
$((a{*}|b)c){*}$ sur l'alphabet $\Sigma = \{a,b,c\}$. On doit obtenir
un automate ayant $4$ états.
@@ -3171,7 +3171,7 @@ celles aboutissant à $3$ sont étiquetées $c$.
\thingy La construction de Glushkov (exposée
en \ref{glushkov-construction}) d'un automate reconnaissant le langage
dénoté par expression rationnelle $r$ fabrique un NFA. Cette
-constrution produit un automate raisonnablement compact (en nombre
+construction produit un automate raisonnablement compact (en nombre
d'états), mais il peut être intéressant de disposer d'une autre
construction, plus transparente mais moins efficace : la
\defin[Thompson (construction d'automate de)]{construction de
@@ -3661,7 +3661,7 @@ n'existait pas au départ, lorsqu'on peut arriver de l'un vers l'autre
en passant par $q$. Et il faut se souvenir que le cas $q_2=q_1$ est à
traiter aussi.
-En général, l'élimination des états conduit à un expression
+En général, l'élimination des états conduit à une expression
extrêmement compliquée (exponentielle dans le nombre d'états de
l'automate, au moins dans le pire cas, mais aussi dans beaucoup de cas
« typiques »).
@@ -3786,7 +3786,7 @@ $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.
Il s'agit d'un automate « compteur limité », qui ne sait compter que
de $0$ à $4$, incrémentant son compteur quand il reçoit un $a$ et le
-décrementant quand il reçoit un $b$ (et cessant de fonctionner si le
+décrémentant quand il reçoit un $b$ (et cessant de fonctionner si le
compteur passe au-dessus du maximum ou en-dessous du minimum), et qui
accepte finalement les mots dont le nombre de $b$ égale le nombre
de $a$ sans qu'il y ait jamais eu plus de $b$ que de $a$ ni plus de
@@ -4208,7 +4208,7 @@ de \ref{myhill-nerode} on vérifie qu'elle préserve l'état initial, les
l'automate minimal en fusionnant chaque classe d'équivalence
pour $\equiv$.
-Montrons maintenant comment on peut construre $\equiv$
+Montrons maintenant comment on peut construire $\equiv$
algorithmiquement. Pour cela, on va définir des relations
d'équivalence $\equiv_i$ pour $i\in\mathbb{N}$ par
\[
@@ -4814,7 +4814,7 @@ $(q_{i-1},t_i,q_i) \in \delta$ pour $1\leq i\leq n$, suivie
lorsque $q_n \in F$. Manifestement, les dérivations de la sorte
(terminant sur un mot sur $\Sigma$) sont en bijection avec les chemins
$q_0 \to \cdots \to q_n$ dans $A$ où $q_n \in F$, et le mot $t_1\cdots
-t_n$ dérivé est précisément le mot formé en concacténant les
+t_n$ dérivé est précisément le mot formé en concaténant les
étiquettes du chemin. On a donc bien $L(G) = L(A)$.
\end{proof}
@@ -5523,7 +5523,7 @@ On a vu en §\ref{subsection-pumping-lemma} une condition nécessaire
que doivent vérifier les langages rationnels, et qui est souvent utile
pour montrer qu'un langage \emph{n'est pas} rationnel. Un lemme tout
à fait analogue existe pour les langages algébriques, est qui s'avère
-utile dans des circonstance semblables, même si son emploi est plus
+utile dans des circonstances semblables, même si son emploi est plus
difficile ; on prendra garde au fait que, dans l'énoncé suivant,
$x$ et $y$ désignent des mots et non des lettres comme d'habitude :
@@ -6580,7 +6580,7 @@ numéro $e$ en entrée, i.e., si $\varphi_e(e)\downarrow$, (2º) si oui,
effectuer une boucle infinie, et si non, terminer, en renvoyant,
disons, $42$. L'algorithme qui vient d'être décrit aurait un certain
numéro, disons, $p$, et la description de l'algorithme fait que,
-quelque soit $e$, la valeur $\varphi_p(e)$ est indéfinie si
+quel que soit $e$, la valeur $\varphi_p(e)$ est indéfinie si
$\varphi_e(e)$ est définie tandis que $\varphi_p(e)$ est définie (de
valeur $42$) si $\varphi_e(e)$ est indéfinie. En particulier, en
prenant $e=p$, on voit que $\varphi_p(p)$ devrait être défini si et