W jaki sposób NFA wykorzystuje przejścia epsilon?

Na poniższym zdjęciu próbuję dowiedzieć się, co dokładnie akceptuje ten NFA.

To, co mnie dezorientuje, to skok przy . $\epsilon$ $q_0$

Jeśli zostanie wprowadzone , czy system przejdzie zarówno do i do (stan akceptacji)? $0$ $q_0$ $q_1$
Jeśli wprowadzona zostanie , czy system przejdzie zarówno do i do ? $1$ $q_1$ $q_2$
Czy system przechodzi do (stan akceptacji), jeśli nie podano danych wejściowych (pusty ciąg)? $q_1$

automata finite-automata nondeterminism

Wróć do definicji: NFA akceptuje słowo, jeśli akceptuje je dowolne obliczenie. NFA jako takie nie są „algorytmami” w tym sensie, że DFA.

— Raphael

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

Jeśli ciąg ma wartość wówczas automaty kończą się na i $\epsilon$ $q_0$ $q_1$

Jeśli Twój ciąg ma wartość „0”, będzie ponownie w i $q_0$ $q_1$

Jeśli twój ciąg to „1”, będzie tylko w , ponieważ jeśli spojrzysz od punktu , masz przejście „1” do , ale musisz również spojrzeć na przypadek, w którym jesteś w (jeśli byłeś w , zawsze byłeś w ), wówczas nie ma przejścia „1”, więc ta alternatywna ścieżka po prostu „umiera”. $q_2$ $q_0$ $q_2$ $q_1$ $q_0$ $q_1$

Wystarczy spojrzeć na te przypadki i łatwo zauważyć, że automaty akceptują , i przechodząc od do , jedynym sposobem na osiągnięcie jest , więc wznawia to automaty do , , $\epsilon$ $0^*$ $q_0$ $q_1$ $q_2$ $0^*11^*1$ $\epsilon$ $0^*$ $0^*11^*1$

Mam nadzieję, że pomogło ci to, jeśli masz dalsze wątpliwości, po prostu zapytaj!

— H_DANILO
źródło

„oznacza to, że automatycznie znajdujesz się w OBU stanach” - nie sądzę, że jest to pomocna intuicja, tzn. reprezentuje niedeterminizm w niewłaściwy sposób.

— Raphael

Dlaczego to źle reprezentuje? Cóż, zgodnie z definicją delty niedeterminizmu, otrzymujesz zestaw stanów zamiast tylko 1 poprawnie? Może to oznaczać tylko, że jesteś w obu stanach.

— H_DANILO

Promuje ideę, że niedeterministyczne maszyny „wypróbowują wszystkie rozwiązania równolegle”. Nie tak się dzieje, mówiąc algorytmicznie. Niedeterminizm jest formalizmem opisowym, a nie techniką algorytmiczną.

— Raphael

Próbowałem przedstawić to w zrozumiały sposób, ponieważ stara się on teoretycznie zrozumieć zasady niedeterminizmu

— H_DANILO,

@Raphael Jaka byłaby Twoim zdaniem bardziej pomocna intuicja?

— Andrey Portnoy

$q_0$ $q_0$ $q_1$ $q_1$

$q_0$ $0$ $q_0$ $q_1$ $0$ $q_0$ $1$ $q_2$ $1$ $q_1$ $q_1$ $1$

$0^*+0^*11^*1$ $0$ $1$

$\epsilon$ $\epsilon$

— Rick Decker
źródło

-1

Próbowałem skonstruować DFA dla tego NFA

$\sum$

$Q$

$\sigma(Q\times (\sum \cup {\epsilon} )) \to P(Q)$

$q_0 = q_0$

$F \subseteq Q, F = \{q_0\}$

$M'$

alfabet - to samo

$Q' = P(Q)$

$R \in P(Q)$

$E(R)$ $\epsilon$ $r \in R$

$\sigma'(R,a) = \bigcup_{r \in R} E(\sigma(r,a))$

$q'_{0} = E(\{q_0\})$

$F' = P(Q) \div F$

Niektóre obliczają na tym FSM

$1.$ $\epsilon$ $q'_{0} = E(\{q0\}) = \{q_0, q_1\}$ $q_1$ $\epsilon$

$2.$ $0*$ $\sigma'(\{q_0, q_1\}, 0) = E(\sigma(q_0,0)) \cup E(\sigma(q_1,0)) = \{q_0, q_1\} \cup \{ \} = \{q_0, q_1\}$ $0*$

$\{\epsilon, 0* \} \subset L (M')$

Dzięki David Richerby

— OrangeFish
źródło

Dzięki za podziękowania, ale tak naprawdę nie rozumiem, jak to odpowiada na pytanie. Nie ustaliłeś, jaki język akceptuje maszyna, ani nie odpowiedziałeś na żadne z trzech wypunktowanych pytań.

— David Richerby

ϵ

$\epsilon$

{q_{0}, q_{1}}

$\{q_0, q_1\}$

0

$0$

0 *

$0*$

{q_{0}, q_{1}}

$\{q_0, q_1\}$