Autómatas finitos no deterministas

Autómatas finitos no deterministas | Sipser Ejemplo 1.16

Estoy trabajando en el Libro Sipser (2ª edición) y encontré este ejemplo, que no entiendo. En el libro dice que este NFA acepta la cadena vacía, $\epsilon$ .

¿Podría alguien explicarme por qué este es el caso?

Tengo entendido que $\epsilon$ se moverá a $q_3$ que no es un estado de aceptación.

regular-languages finite-automata nondeterminism Leopardo convexo
fuente

ϵ

$\epsilon$

Gracias por los enlaces completos, creo que ahora entiendo esto.

Convex Leopard

Respuestas:

$\epsilon$

$w$ $w$ $w$

q_{0} \overset{w_{1}}{\to} q_{1} \overset{w_{2}}{\to} q_{2} \overset{w_{3}}{\to} \dots \overset{w_{n}}{\to} q_{n}

$q_0 \stackrel{w_1}\to q_1 \stackrel{w_2}\to q_2 \stackrel{w_3}\to \cdots \stackrel{w_n}\to q_n$

$q_0$
$q_n$
$q_{i-1} \stackrel{w_i}\to q_i$
$w = w_1 \ldots w_n$

$\epsilon$ $\epsilon$

$\epsilon$

q_{0} \overset{ϵ}{\to} q_{1} \overset{ϵ}{\to} \dots \overset{ϵ}{\to} q_{n}

$q_0 \stackrel\epsilon\to q_1 \stackrel\epsilon\to \cdots \stackrel\epsilon\to q_n$

q_{0}

$q_0$

q_{n}

$q_n$

ϵ

$\epsilon$

n = 0

$n = 0$

Yuval Filmus
fuente

ϵ

$\epsilon$

q 1 \to q 1

$q1 \rightarrow q1$

q 1 \to q 3

$q1 \rightarrow q3$

q 1 \to q 1

$q1 \rightarrow q1$

ϵ

$\epsilon$

Sí, esa es una buena descripción.

Yuval Filmus