diff options
| -rw-r--r-- | notes-inf105.tex | 23 |
1 files changed, 12 insertions, 11 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 2131cb3..67a0a9b 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2757,11 +2757,11 @@ $(\varphi_2(q),x,q')$ où $(q,x,q') \in \delta_2$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe -de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$, -puis en éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$ -et $q_2$ devenus inutiles. Cela donne le même résultat que ce qui -vient d'être dit.) +de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$ +(qui cessent d'être initiaux), puis en éliminant les ε-transitions +qu'on vient d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi +que les états $q_1$ et $q_2$ devenus inutiles. Cela donne le même +résultat que ce qui vient d'être dit.) Il est alors clair qu'un chemin de l'état initial à un état final dans cet automate $A'$ consiste soit en un chemin d'un état initial à un @@ -2788,7 +2788,8 @@ L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant chaque transition sortant de $q_2$ par une transition identiquement étiquetée, et de même cible, partant de \emph{chaque} état final -de $A_1$. Graphiquement : +de $A_1$ (ces derniers seront marqués finaux si $q_2$ était final +dans $A_2$). Graphiquement : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)] @@ -2861,11 +2862,11 @@ $(q,x,q')$ tels que $(q_2,x,q') \in \delta_2$ et que $q\in F_1$. (\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une -ε-transition de chaque état final de $A_1$ vers $q_2$, puis en -éliminant les ε-transitions qu'on vient d'ajouter -(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$ -devenu inutile. Cela donne le même résultat que ce qui vient d'être -dit.) +ε-transition de chaque état final de $A_1$ vers $q_2$ (qui cesse +d'être initial), puis en éliminant les ε-transitions qu'on vient +d'ajouter (cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état +$q_2$ devenu inutile. Cela donne le même résultat que ce qui vient +d'être dit.) Il est alors clair qu'un chemin de l'état initial $q_1$ à un état final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état |