Niedeterministyczne automaty skończone | Przykład Sipser 1.16

9

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 .ϵ

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

Rozumiem, że przejdzie do co nie jest stanem akceptacji.ϵq3)

wprowadź opis zdjęcia tutaj

Wypukły lampart
źródło
1
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? ϵ
John L.,
Dzięki za wyczerpujące linki - myślę, że teraz to rozumiem.
Wypukły lampart

Odpowiedzi:

10

Mylisz z listem. To nie jest list! To tylko pusty ciąg.ϵ

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:www

q0w1q1w2)q2)w3)wnqn

  1. q0 jest stanem początkowym. (Zwykły model dopuszcza tylko jeden stan początkowy, ale możemy złagodzić ten wymóg).
  2. qn to stan końcowy (zwany także stanem akceptującym).
  3. Każde przejście odpowiada przejściu słowa-NFA.qja-1wjaqja
  4. w=w1wn .

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.ϵϵ

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 ).ϵ

q0ϵq1ϵϵqn
q0qnϵn=0

Yuval Filmus
źródło
AHA, dziękuję, to ma teraz sens. Tak intuicyjnie, kiedy się pojawiϵ mamy dwie „gałęzie”: q1q1 i q1q3). Odq1q1 jest stanem akceptacji, akceptujemy ϵ
Wypukły lampart
1
Tak, to fajny opis.
Yuval Filmus