From 10559224d661e323fb4fe10957583339a76ed98a Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 28 Nov 2017 10:40:57 +0100 Subject: Fix proof of standardization of automata. The case where the added state should have been final was missing. Thanks to Antoine for pointing this out. --- notes-inf105.tex | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/notes-inf105.tex b/notes-inf105.tex index 68feda3..852c98a 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2606,13 +2606,16 @@ initial de $A$, on ajoute dans $A'$ une transition identiquement étiquetée, et de même cible, partant de $q_0$. Formellement : soit $A = (Q,I,F,\delta)$. On définit alors $A' = -(Q',\{q_0\},F,\delta')$ de la manière suivante : $Q' = Q \uplus +(Q',\{q_0\},F',\delta')$ de la manière suivante : $Q' = Q \uplus \{q_0\}$ (où $\uplus$ désigne une réunion disjointe\footnote{C'est-à-dire qu'on exige que $q_0$ n'appartienne - pas à $Q$ (c'est un nouvel état).}), et $\delta'$ est la réunion de + pas à $Q$ (c'est un nouvel état).}), $\delta'$ est la réunion de l'ensemble des transitions $(q,x,q')$ qui étaient déjà dans $\delta$ et de l'ensemble des $(q_0,x,q')$ telles qu'il existe une transition -$(q,x,q') \in \delta$ avec $q\in I$. +$(q,x,q') \in \delta$ avec $q\in I$, et enfin $F' = F$ ou $F' = +F\cup\{q_0\}$ selon que $I\cap F = \varnothing$ ou $I\cap F \neq +\varnothing$ respectivement (i.e., $q_0$ est final lorsqu'il existait +déjà un état à la fois initial et final). La figure suivante illustre la transformation en question : \begin{center} -- cgit v1.2.3