Nicht deterministische endliche Automaten Sipser Beispiel 1.16

Ich arbeite mich durch das Sipser-Buch (2. Auflage) und bin auf dieses Beispiel gestoßen, das ich nicht verstehe. In dem Buch heißt es, dass diese NFA die leere Zeichenfolge $\epsilon$ akzeptiert .

Könnte mich jemand durchgehen lassen, warum dies der Fall ist?

Mein Verständnis ist, dass $\epsilon$ zu $q_3$ was kein Akzeptanzzustand ist.

regular-languages finite-automata nondeterminism Konvexer Leopard
quelle

ϵ

$\epsilon$

Vielen Dank für die umfassenden Links - ich glaube, ich verstehe das jetzt.

Konvexer Leopard

Antworten:

$\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
quelle

ϵ

$\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$

Ja, das ist eine schöne Beschreibung.

Yuval Filmus