Es $(p,\epsilon,p)$ un camino de un autómata?

Question

$A$ es un alfabeto. Un autómata $A$ puede ser definido como un conjunto $A_0 = (Q, E, I, T),$ donde $Q$ es el conjunto de los estados, $E \subseteq Q \times A \times Q$ es la conjunto de aristas o de transición, $I, T \subseteq Q$ de estados inicial y terminal. Un camino en el autómata $A_0$ es una secuencia $(p_0, a_1, p_1),$ $(p_1, a_2, p_2),$ $\ldots,$ $(p_{n-1}, a_n, p_n)$ consecutivos en los bordes. Un estado $p$ es accesible si hay un camino de salida en un estado inicial y final en $p.$ es coaccessible si hay un camino que comienza en $p$ y terminar en una terminal estado. Un autómata es recortar si cada estado es accesible y coacessible.

La información de arriba es de M. Lothaire del Algebraicas La combinatoria de las Palabras. Mi pregunta es si $(p, \epsilon, p)$ es una ruta de acceso o no. Desde $\epsilon$ es no en $A,$ mi respuesta es no. Si es así, es un estado inicial accesible? De acuerdo a la definición anterior, podemos dicen que si hay una ruta a partir de un estado inicial y final en el estado inicial.Entonces, si de un autómata se recorte,los estados iniciales deben ser accesibles.Pero en la siguiente declaración sobre el recorte de los autómatas,no creo que el $trim$ asegura que el estado inicial(s) es(son) necesarios accesible.

Lo que en realidad lo quiero para asegurarse de si el $(p,\epsilon,p)$ es un camino. En segundo lugar, si los estados iniciales son sólo coaccessible(he.e no puede ser de ninguna ruta de acceso a partir de un estado inicial y final en los estados iniciales), es el autómata todavía trim?

Estas dos preguntas me hacen demasiado confundido como para seguir leyendo el siguiente contenido en el libro. Gracias de antemano.

---

Si me aplican $\epsilon$ en la definición.A continuación, el ejemplo de la primera regresa al estado 1, a continuación, que no debería ser $X=${$b,ab$} pero $X=${$\epsilon,b,ab$} lo que se contradice con la ex $X=${$b,ab$} dado en el libro.El conjunto de $first$ $returns$ a un estado de $q$ es el conjunto de etiquetas(o palabras) de las rutas de $q$ $q$que no pase otra vez a través de $q$.

Por otro lado,sin el $\epsilon$ camino,no sé cómo asegurarse de que el autómata en la siguiente prueba es recortar,dado que el estado inicial no parece ser accesibles sin el $\epsilon$ camino.

---

Toda la información anterior se muestra en http://x.co/iEVa, a partir de la Página 12 Página 14.
Gracias por leer este largo post.

Answer 1

La definición de un camino no dice que la secuencia no puede ser una secuencia vacía. Pero entonces, es molesto para preguntar "¿cuál es el punto de partida de la secuencia vacía ?", y el texto no es claro que. Es la copa de tener una ruta vacía de cada estado en sí mismo :

Una definición más clara puede ser : un camino de $p$ $q$es una secuencia finita de estados $(p_0, \ldots, p_n)$, con una palabra de longitud $n$, $w = a_1 \ldots a_n$ tal que $p=p_0, q=p_n,$ $(p_{i-1}, a_i,p_i) \in E$ todos los $i \in \{1 \ldots n\}$.

Con esta definición, claramente se puede tener vacío rutas de acceso de un estado a sí mismo, y el "estado inicial" y "final" de una ruta de acceso es una parte de la definición, así que usted puede utilizar para la discusión que sigue. Y, en particular, todos los estados iniciales son accesibles, y todos los estados finales son coaccessible.

También, si el autómata no determinista, no avisable para describir una ruta de acceso con sólo el estado inicial, el fin del estado, y la palabra $w$ asociado a la ruta, ya que no necesariamente a decir lo que son todos los estados intermedios.

---

En la Proposición 1.3.2, el texto sugiere que $Q(\epsilon)$ debe ser definido desde la palabra vacía es una palabra, así que el conjunto $Q(\epsilon)$ estados $q$ para los que hay un camino a partir de un estado inicial a $q$ cuyos asociados palabra es $\epsilon$ debe ser significativa (de hecho, consigue $Q(\epsilon) =\{I\}$ )

Otro problema es que el $\mathscr{B}$ pueden tener los estados que no son coaccessible. Cada estado $Q(u)$ es accesible desde $\{I\}$, con una ruta cuyo asociados palabra es $u$. Pero si, por ejemplo, no hay ningún terminal de estado en el primer lugar, entonces usted no consigue ningún estado de terminal server en $\mathscr{B}$, por lo que el estado no es coaccessible. Si quita todos los que no coaccessible estados de $\mathscr{B}$, a continuación, obtener un recorte de los autómatas.

Por ejemplo, un recorte de los autómatas, reconociendo el vacío del lenguaje es $(\emptyset, \emptyset, \emptyset, \emptyset)$

---

Para el conjunto de las primeras devoluciones, sí parece que, por el contrario, vacío etiquetas o vacío caminos no están permitidos en la definición del conjunto de rendimientos en primer lugar.

Así que usted tiene que tener cuidado y activamente comprobar si el autor permite "la ruta vacía" en cualquier definición que implican caminos, y escoger el que hace la siguiente explicación coherente. Desde mi limitada experiencia, es generalmente permitido. A pesar de que este libro parece haber una gama bastante amplia de temas, así que no puedo divina que es siempre el caso.

Tenga en cuenta que es muy difícil (imposible leer) para escribir un libro entero sin hacer un par de errores / omisiones aquí y allá, especialmente en casos extremos como este.