diff options
| -rw-r--r-- | notes-inf105.tex | 67 |
1 files changed, 22 insertions, 45 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 5bce718..ead466a 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1874,22 +1874,27 @@ symbole « $\varepsilon$ » pour étiqueter les transitions spontanées). Un NFA est considéré comme un εNFA particulier pour lequel il n'y a pas de ε-transition. -\thingy Un εNFA accepte un mot $w$ lorsqu'il existe un chemin -conduisant d'un état initial à un état final et dont les arêtes sont -étiquetées par les lettres de $w$ ou bien des $\varepsilon$ insérés à -n'importe quel endroit et en n'importe quel nombre. Autrement dit, -$w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ et -$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ tels que $q_0 \in I$ -et $q_n\in F$ et $(q_{i-1},t_i,q_i) \in \delta$ pour chaque $1\leq -i\leq n$ et $w = t_1\cdots t_n$ (\emph{attention} : dans cette -écriture, $t_1,\ldots,t_n$ ne sont pas forcément les lettres de $w$, -certains des $t_i$ peuvent être le symbole $\varepsilon$, les lettres -de $w$ sont obtenues en ignorant ces symboles). - -De façon plus intuitive, cela signifie que l'automate a la possibilité -de passer spontanément, c'est-à-dire sans consommer de lettre, d'un -état $q$ à un état $q'$, lorsque ces états sont reliés par une -ε-transition. +\thingy Intuitivement, les transitions spontanées signifient que +l'automate a la possibilité de passer spontanément, c'est-à-dire +\emph{sans consommer de lettre}, d'un état $q$ à un état $q'$, lorsque +ces états sont reliés par une ε-transition. (On comprend, du coup, +pourquoi un automate à transition spontanée est forcément +non-déterministe : ces transitions spontanées ne sont qu'une +\emph{possibilité}, ce qui sous-entend le non-déterminisme.) + +De façon plus précise, un εNFA accepte un mot $w$ lorsqu'\emph{il + existe} un chemin orienté conduisant d'un état initial $q_0$ à un +état final $q_n$ et tel que $w$ coïncide avec le mot obtenu en lisant +dans l'ordre les étiquettes $x_i$ des différentes arêtes $q_{i-1} \to +q_i$ de ce chemin, quitte à ignorer les $\varepsilon$. + +Autrement dit, $w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n +\in Q$ et $t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ tels que +$q_0 \in I$ et $q_n\in F$ et $(q_{i-1},t_i,q_i) \in \delta$ pour +chaque $1\leq i\leq n$ et $w = t_1\cdots t_n$ (\emph{attention} : dans +cette écriture, $t_1,\ldots,t_n$ ne sont pas forcément les lettres +de $w$, certains des $t_i$ peuvent être le symbole $\varepsilon$, les +lettres de $w$ sont obtenues en ignorant ces symboles). \thingy Voici une formalisation possible : si $A = (Q,I,F,\delta)$ est un εNFA sur l'alphabet $\Sigma$, on définit une relation $\delta^* @@ -1899,34 +1904,6 @@ lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $t_1,\ldots,t_n \in $(q_{i-1},t_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w = t_1\cdots t_n$. -Si on préfère, on peut définir par récurrence sur $n \geq 0$ une -relation $\delta^{(n)} \subseteq Q \times \Sigma^* \times Q$ de la -manière suivante : -\begin{itemize} -\item $(q,w,q') \in \delta^{(0)}$ si et seulement si $q'=q$ et - $v=\varepsilon$, -\item $\delta^{(1)} = \delta \subseteq Q \times - (\Sigma\cup\{\varepsilon\})$ (faisant partie de la donnée de $A$), -\item $(q,v,q') \in \delta^{(n+1)}$ si et seulement si il existe - $q^\sharp \in Q$ et $t \in \Sigma\cup\{\varepsilon\}$ tels que - $(q,w,q^\sharp) \in \delta^{(n)}$ et $(q^\sharp,t,q') \in \delta$ et - $v = wt$ (ce qui signifie que : soit $t=\varepsilon$ et $v=w$, soit - $t\in\Sigma$ est la dernière lettre de $w$ et $v$ est le préfixe - correspondant) ; -\end{itemize} -et on définit $\delta^* = \bigcup_{n=1}^{+\infty} \delta^{(n)}$, -autrement dit $(q,w,q') \in \delta^*$ lorsqu'il existe $n$ tel que -$(q,w,q') \in \delta^{(n)}$. - -Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le εNFA peut -passer de l'état $q$ à l'état $q'$ en effectuant (exactement) $n$ -transitions ($q_0\to q_1 \to \cdots \to q_n$ étiquetées par -$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$) et en consommant le -mot $w$ (soit $w = t_1\cdots t_n$) ; et $(q,w,q') \in \delta^*$ -signifie la même chose mais sans contrainte sur le nombre de -transitions. La différence avec les NFA est que le nombre $n$ de -transitions n'est plus forcément égal à la longueur de $w$. - Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$ et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. Le langage accepté $L_A$ et l'équivalence de deux automates sont définis @@ -2408,7 +2385,7 @@ lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $r_1,\ldots,r_n \in $(q_{i-1},r_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w \in L_{r_1\cdots r_n}$. -Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le RNFA peut +Concrètement, $(q,w,q') \in \delta^*$ signifie que le RNFA peut passer de l'état $q$ à l'état $q'$ en effectuant des transitions ($q_0\to q_1 \to \cdots \to q_n$ étiquetées par $r_1,\ldots,r_n \in \mathrm{regexp}(\Sigma)$) et en consommant le mot $w$ au sens où ce |