Na poniższym zdjęciu próbuję dowiedzieć się, co dokładnie akceptuje ten NFA.
To, co mnie dezorientuje, to skok przy q 0 .
Jeśli zostanie wprowadzone , czy system przejdzie zarówno do q 0, jak i do q 1 (stan akceptacji)?
Jeśli wprowadzona zostanie , czy system przejdzie zarówno do q 1, jak i do q 2 ?
Czy system przechodzi do (stan akceptacji), jeśli nie podano danych wejściowych (pusty ciąg)?
automata
finite-automata
nondeterminism
użytkownik3472798
źródło
źródło
Odpowiedzi:
Za każdym razem, gdy jesteś w stanie, który ma przejście , oznacza to, że automatycznie znajdujesz się w OBU, aby uprościć ci to:ϵ
Jeśli ciąg ma wartość wówczas automaty kończą się na q 0 i q 1ϵ q0 q1
Jeśli Twój ciąg ma wartość „0”, będzie ponownie w i q 1q0 q1
Jeśli twój ciąg to „1”, będzie tylko w , ponieważ jeśli spojrzysz od punktu q 0 , masz przejście „1” do q 2 , ale musisz również spojrzeć na przypadek, w którym jesteś w q 1 (jeśli byłeś w q 0 , zawsze byłeś w q 1 ), wówczas nie ma przejścia „1”, więc ta alternatywna ścieżka po prostu „umiera”.q2 q0 q2 q1 q0 q1
Wystarczy spojrzeć na te przypadki i łatwo zauważyć, że automaty akceptują , 0 ∗ i przechodząc od q 0 do q 1 , jedynym sposobem na osiągnięcie q 2 jest 0 ∗ 11 ∗ 1 , więc wznawia to automaty do ϵ , 0 ∗ , 0 ∗ 11 ∗ 1ϵ 0∗ q0 q1 q2 0∗11∗1 ϵ 0∗ 0∗11∗1
Mam nadzieję, że pomogło ci to, jeśli masz dalsze wątpliwości, po prostu zapytaj!
źródło
źródło
Próbowałem skonstruować DFA dla tego NFA
alfabet - to samo
Niektóre obliczają na tym FSM
Dzięki David Richerby
źródło