Niedeterministyczne automaty skończone

Pracuję nad Sipser Book (wydanie drugie) i natknąłem się na ten przykład, którego nie rozumiem. W książce stwierdzono, że ten NFA akceptuje pusty ciąg . $\epsilon$

Czy ktoś mógłby mnie przekonać, dlaczego tak jest?

Rozumiem, że przejdzie do co nie jest stanem akceptacji. $\epsilon$ $q_3$

regular-languages finite-automata nondeterminism

— Wypukły lampart
źródło

To klasyczne pytanie dotyczące użycia w NFA. Oto pytanie dotyczące tego samego przykładu, co oznacza ciąg wejściowy epsilon? . W NFA-ε istnieje również znaczenie pytania ε? i w jaki sposób NFA wykorzystuje przejścia epsilon?

ϵ

$\epsilon$

— John L.,

Dzięki za wyczerpujące linki - myślę, że teraz to rozumiem.

— Wypukły lampart

Mylisz z listem. To nie jest list! To tylko pusty ciąg. $\epsilon$

Rozważmy nieco bardziej ogólny model, „słowo-NFA”. Słowo-NFA jest jak NFA, ale każde przejście jest oznaczone dowolnym słowem. Mówimy, że słowo-NFA akceptuje słowo jeśli istnieje przejście ze stanu początkowego do stanu końcowego, tak że jeśli połączymy etykiety krawędzi na przejściu, otrzymamy . W symbolach słowo-NFA akceptuje jeśli występuje sekwencja przejść takie, że: $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$ jest stanem początkowym. (Zwykły model dopuszcza tylko jeden stan początkowy, ale możemy złagodzić ten wymóg).
$q_n$ to stan końcowy (zwany także stanem akceptującym).
Każde przejście odpowiada przejściu słowa-NFA. $q_{i-1} \stackrel{w_i}\to q_i$
$w = w_1 \ldots w_n$ .

NFA to słowo-NFA, w którym wszystkie przejścia są oznaczone literami (tj. Słowa o długości dokładnie 1), a -NFA to takie, w którym wszystkie przejścia są oznaczone literami lub (tj. Słowa długości co najwyżej 1). Zwykle wymagamy również, aby istniał unikalny stan początkowy. $\epsilon$ $\epsilon$

Słowo-NFA akceptuje jeśli istnieje sekwencja przejść tak, że jest stanem początkowym, jest stanem końcowym , i wszystkie przejścia są prawidłowe. W szczególności, jeśli jakiś stan jest zarówno początkowy, jak i końcowy, wówczas słowo-NFA akceptuje (odpowiada to ). $\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
źródło

AHA, dziękuję, to ma teraz sens. Tak intuicyjnie, kiedy się pojawi

ϵ

$\epsilon$ mamy dwie „gałęzie”:

q 1 \to q 1

$q1 \rightarrow q1$ i

q 1 \to q 3

$q1 \rightarrow q3$ . Od

q 1 \to q 1

$q1 \rightarrow q1$ jest stanem akceptacji, akceptujemy

ϵ

$\epsilon$

— Wypukły lampart

Tak, to fajny opis.

— Yuval Filmus

Niedeterministyczne automaty skończone | Przykład Sipser 1.16