summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-01 16:46:31 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-11-01 16:46:31 (GMT)
commit82c0f39067062dd072fe9203b30bd92cac7c0cd4 (patch)
tree0dafd448d413ab9cf2cc5edfa8459fa5921b7f85 /notes-inf105.tex
parent449e77b2a547ffd171ea2012a8de96b4afed85b3 (diff)
downloadinf105-82c0f39067062dd072fe9203b30bd92cac7c0cd4.zip
inf105-82c0f39067062dd072fe9203b30bd92cac7c0cd4.tar.gz
inf105-82c0f39067062dd072fe9203b30bd92cac7c0cd4.tar.bz2
Change acronym for incomplete automata to "DFAi" with lowercase i.
Is this really a good idea? Maybe not.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex72
1 files changed, 36 insertions, 36 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 4533160..60881fb 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1497,7 +1497,7 @@ automates déterministes finis incomplets et on va donc commencer par
eux.
-\subsection{Automates finis déterministes à spécification incomplète (=DFAI)}
+\subsection{Automates finis déterministes à spécification incomplète (=DFAi)}
\thingy\label{definition-dfai} Un \textbf{automate fini déterministe à
spécification incomplète} ou \textbf{...partielle}, ou simplement
@@ -1505,9 +1505,9 @@ eux.
incomplet}\footnote{\label{footnote-on-word-incomplete}Le mot
« incomplet » signifie en fait « non nécessairement complet », i.e.,
l'automate a le droit de manquer certaines transitions, il peut très
- bien être complet (un DFA est un DFAI particulier, pas le
- contraire).}, en abrégé \index{DFAI|see{automate fini déterministe
- incomplet}}\textbf{DFAI}, sur un alphabet $\Sigma$ est la donnée
+ bien être complet (un DFA est un DFAi particulier, pas le
+ contraire).}, en abrégé \index{DFAi|see{automate fini déterministe
+ incomplet}}\textbf{DFAi}, sur un alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ d'états,
\item d'un état initial $q_0 \in Q$,
@@ -1525,24 +1525,24 @@ en \ref{definition-dfa} est que la fonction $\delta$ est partielle, ce
qui signifie qu'elle n'est pas obligatoirement définie sur tout couple
$(q,x) \in Q\times\Sigma$.
-Un DFA est considéré comme un DFAI particulier où la fonction de
+Un DFA est considéré comme un DFAi particulier où la fonction de
transition $\delta$ se trouve être définie partout.
-\thingy Graphiquement, on représente un DFAI comme un DFA, à la
+\thingy Graphiquement, on représente un DFAi comme un DFA, à la
différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y
a maintenant \emph{au plus une} (et non plus exactement une) arête
partant de $q$ et étiquetée par $x$.
-L'intérêt informatique des DFAI est de ne pas s'obliger à stocker
+L'intérêt informatique des DFAi est de ne pas s'obliger à stocker
inutilement des transitions et des états inutiles au sens où ils ne
permettront jamais d'accepter le mot (voir la notion d'automate
« émondé » en \ref{coaccessible-and-useful-states} ci-dessous). C'est
la raison pour laquelle, même si les DFA complets sont théoriquement
plus satisfaisants à manier (pour la même raison qu'une fonction
totale est plus satisfaisante qu'une fonction partielle), il est
-souvent algorithmiquement plus judicieux de travailler sur des DFAI.
+souvent algorithmiquement plus judicieux de travailler sur des DFAi.
-\thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à
+\thingy Le fonctionnement d'un DFAi est le même que celui d'un DFA, à
la modification suivante près : si on donne à consommer à l'automate
une lettre pour laquelle la transition n'est pas définie, i.e., s'il
rencontre un $x$ pendant qu'il se trouve dans un état $q$ pour lequel
@@ -1556,12 +1556,12 @@ lorsqu'il existe un chemin orienté dans l'automate, reliant l'état
$q_0$ initial à un état $q_n$ final, et tel que le mot $w = x_1 \cdots
x_n$ soit obtenu en lisant dans l'ordre les étiquettes $x_i$ des
différentes arêtes $q_{i-1} \to q_i$ de ce chemin. La différence des
-DFAI par rapport aux DFA est que, cette fois, la tentative de chemin
+DFAi par rapport aux DFA est que, cette fois, la tentative de chemin
pourrait s'arrêter prématurément (on ne peut plus consommer un symbole
et passer dans un nouvel état, et à plus forte raison, aboutir à un
état final).
-\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFAI sur
+\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFAi sur
l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon
Q\times\Sigma^* \dasharrow Q$ par $\delta^*(q,x_1\cdots x_n) =
\delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ avec la convention
@@ -1586,7 +1586,7 @@ Le langage accepté $L_A$ et l'équivalence de deux automates sont
définis de façon analogue aux DFA
(cf. \ref{definition-recognizable-language}).
-\thingy\label{discussion-example2b} Voici un exemple de DFAI sur
+\thingy\label{discussion-example2b} Voici un exemple de DFAi sur
l'alphabet $\Sigma = \{a,b,c\}$. Cet automate reconnaît exactement
les mots formés d'un nombre quelconque de $c$, suivis d'un $a$, suivis
d'un nombre quelconque de $c$, suivis d'un $b$, suivis d'un nombre
@@ -1615,7 +1615,7 @@ quelconque de $c$.
$c{*}ac{*}bc{*}$.)
\begin{prop}\label{completion-of-dfai}
-Soit $A = (Q,q_0,F,\delta)$ un DFAI sur un alphabet $\Sigma$. Alors
+Soit $A = (Q,q_0,F,\delta)$ un DFAi sur un alphabet $\Sigma$. Alors
il existe un DFA $A' = (Q',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
@@ -1639,7 +1639,7 @@ définit $\delta'(q,x)$ pour $q\in Q'$ et $x\in\Sigma$ par
Il est alors facile de voir que $A'$ a le même comportement que $A$ au
sens où $\delta^{\prime*}(q,w) = \delta^*(q,w)$ lorsque le terme de
droite est défini et $\delta^{\prime*}(q,w) = q_\bot$ sinon (le DFA
-$A'$ « tombe dans le puits » lorsque le DFAI $A$ cesse de
+$A'$ « tombe dans le puits » lorsque le DFAi $A$ cesse de
fonctionner). En particulier, ils reconnaissent les mêmes langages.
\end{proof}
@@ -1648,7 +1648,7 @@ DFA est un état $q_\bot$ tel que $\delta(q_\bot,x)=q_\bot$ pour toute
lettre $x$.
On dit que le DFA $A'$ est obtenu en \defin[compléter (un
- DFAI)]{complétant} le DFAI $A$ lorsqu'il est obtenu par la procédure
+ DFAi)]{complétant} le DFAi $A$ lorsqu'il est obtenu par la procédure
décrite dans la démonstration de cette proposition, c'est-à-dire par
l'addition d'un état puits vers lequel on fait pointer toutes les
transitions manquantes (sauf si $A$ est déjà complet, auquel cas on
@@ -1656,7 +1656,7 @@ convient qu'il est son propre complété, i.e., on n'ajoute un puits que
quand c'est réellement nécessaire).
\thingy À titre d'exemple, le DFA suivant représente la complétion du
-DFAI représenté en \ref{discussion-example2b} :
+DFAi représenté en \ref{discussion-example2b} :
\begin{center}
%%% begin example2c %%%
@@ -1691,10 +1691,10 @@ DFAI représenté en \ref{discussion-example2b} :
\end{center}
\thingy\label{coaccessible-and-useful-states} On définit un état
-accessible d'un DFAI comme pour un DFA
+accessible d'un DFAi comme pour un DFA
(cf. \ref{definition-dfa-accessible-state}).
-On dira en outre d'un état $q$ d'un DFAI qu'il est
+On dira en outre d'un état $q$ d'un DFAi qu'il est
\defin[co-accessible (état)]{co-accessible} lorsqu'il existe un mot $w
\in \Sigma^*$ tel que $\delta(q,w)$ soit défini et soit final,
autrement dit, graphiquement, lorsqu'il existe un chemin orienté
@@ -1703,15 +1703,15 @@ finaux eux-mêmes sont co-accessibles : prendre $w=\varepsilon$ dans ce
qu'on vient de dire). Un état non co-accessible est donc un état à
partir duquel il est impossible de faire accepter le mot. Cette
définition pourrait également être faite pour les DFA, mais pour les
-DFAI elle présente l'intérêt qu'on peut supprimer les états
-non co-accessibles dans un DFAI (ainsi, bien sûr, que toutes les
+DFAi elle présente l'intérêt qu'on peut supprimer les états
+non co-accessibles dans un DFAi (ainsi, bien sûr, que toutes les
transitions qui y conduisent).
-Un DFAI dont tous les états sont à la fois accessibles et
+Un DFAi dont tous les états sont à la fois accessibles et
co-accessibles (on les dit aussi \defin[utile (état)]{utiles}) est
parfois appelé \defin[émondé (automate)]{émondé}. On peut émonder un
-DFAI en ne conservant que ses états utiles : ainsi, tout DFAI est
-équivalent à un DFAI émondé.
+DFAi en ne conservant que ses états utiles : ainsi, tout DFAi est
+équivalent à un DFAi émondé.
\thingy Il faut prendre garde au fait que certains auteurs définissent
les « automates finis déterministes » (sans précision supplémentaire)
@@ -1773,12 +1773,12 @@ déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire
à un ensemble $\delta$ quelconque de triplets $(q,x,q')$ pour les
transitions possibles.
-\thingy Un DFAI (ou \textit{a fortiori} un DFA) est considéré comme un
+\thingy Un DFAi (ou \textit{a fortiori} un DFA) est considéré comme un
NFA particulier en définissant l'ensemble des états initiaux du NFA
-comme un singleton, $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAI}}\}$, et
+comme un singleton, $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAi}}\}$, et
en définissant la relation de transition du NFA comme le graphe de la
-fonction de transition du DFAI, c'est-à-dire $(q,x,q') \in
-\delta_{\mathrm{NFA}}$ lorsque $\delta_{\mathrm{DFAI}}(q,x)$ est
+fonction de transition du DFAi, c'est-à-dire $(q,x,q') \in
+\delta_{\mathrm{NFA}}$ lorsque $\delta_{\mathrm{DFAi}}(q,x)$ est
défini et vaut $q'$.
\thingy Graphiquement, on représente un NFA comme un DFA : comme un
@@ -1798,14 +1798,14 @@ lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0 \in I$ et
$q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq
n$.
-La différence cruciale avec les DFAI est donc que, maintenant, il
+La différence cruciale avec les DFAi est donc que, maintenant, il
pourrait exister plusieurs chemins possibles partant d'un état initial
dont les transitions sont étiquetées par les lettres du même mot.
Insistons bien sur le fait que le mot est accepté dès lors que
\emph{l'un} au moins de ces chemins relie un état initial à un état
final.
-\thingy De même que dans le cadre des DFA et DFAI on a étendu la
+\thingy De même que dans le cadre des DFA et DFAi on a étendu la
fonction de transition $\delta$ à une fonction $\delta^*$ qui décrit
le comportement de l'automate quand on consomme plusieurs caractères
(cf. \ref{definition-multiple-transition-function}), on va étendre la
@@ -1871,7 +1871,7 @@ pouvoir accepter le mot.
\medbreak
-Comme les DFAI avant eux, les NFA sont en fait équivalents aux DFA ;
+Comme les DFAi avant eux, les NFA sont en fait équivalents aux DFA ;
mais cette fois-ci, le coût algorithmique de la transformation peut
être bien plus important :
@@ -2298,7 +2298,7 @@ simplifie la description).
(langage)}reconnaissable comme un langage $L$ pour lequel il existe
un DFA $A$ tel que $L = L_A$. D'après \ref{completion-of-dfai},
\ref{determinization-of-nfa} et \ref{removal-of-epsilon-transitions},
-on peut remplacer « DFA » dans cette définition par « DFAI », « NFA »
+on peut remplacer « DFA » dans cette définition par « DFAi », « NFA »
ou « εNFA » sans changer la définition.
Nous allons maintenant montrer que les langages reconnaissables sont
@@ -2383,7 +2383,7 @@ symboles.
La construction de l'automate produit pour fabriquer le langage
intersection utilise la caractérisation des langages reconnaissables
-par les DFA : elle aurait aussi fonctionné pour les DFAI mais pas pour
+par les DFA : elle aurait aussi fonctionné pour les DFAi mais pas pour
les NFA ; il est intéressant de réfléchir à pourquoi. (Une
construction du type produit pourrait fonctionner sur les NFA pour le
langage réunion, mais elle n'a aucun intérêt par rapport à la
@@ -3307,7 +3307,7 @@ langage accepté $L_A$ et l'équivalence de deux automates sont définis
de façon analogue aux DFA
(cf. \ref{definition-recognizable-language}).
-\thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAI ou DFA) est
+\thingy Un εNFA (ou \textit{a fortiori} un NFA, DFAi ou DFA) est
considéré comme un RNFA particulier dont les transitions sont
étiquetées soit par une unique lettre (considérée comme expression
rationnelle) soit par le symbole $\underline{\varepsilon}$ (dénotant
@@ -3335,7 +3335,7 @@ S'il n'y a \emph{aucune} transition de $q$ vers $q'$, on peut toujours
choisir d'en ajouter une $(q,\bot,q')$ (qui ne peut pas être
empruntée !) si c'est commode.
-Comme les εNFA, les NFA et les DFAI avant eux, les RNFA peuvent se
+Comme les εNFA, les NFA et les DFAi avant eux, les RNFA peuvent se
ramener aux automates précédemment définis :
\begin{prop}
@@ -3394,7 +3394,7 @@ expressions rationnelles !
\begin{prop}\label{recognizable-languages-are-rational}
Soit $A = (Q,I,F,\delta)$ un RNFA (ou, en particulier, un NFA ou
-DFA(I)) sur un alphabet $\Sigma$. Alors il existe une expression
+DFA(i)) sur un alphabet $\Sigma$. Alors il existe une expression
rationnelle $r$ sur $\Sigma$ qui dénote le langage reconnu par $A$,
soit $L_r = L_A$. De plus, $r$ se déduit algorithmiquement de $A$.
\end{prop}
@@ -3585,7 +3585,7 @@ $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.
\medbreak
-\thingy Donnons encore l'exemple du DFAI suivant :
+\thingy Donnons encore l'exemple du DFAi suivant :
\begin{center}
%%% begin example10 %%%