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.
regular-languages
finite-automata
nondeterminism
Wypukły lampart
źródło
źródło
Odpowiedzi:
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:w w w q0→w1q1→w2)q2)→w3)⋯→wnqn
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 q0 qn ϵ n = 0
źródło