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


12

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

wprowadź opis zdjęcia tutaj

To, co mnie dezorientuje, to skok przy q 0 .ϵq0

  • Jeśli zostanie wprowadzone , czy system przejdzie zarówno do q 0, jak i do q 1 (stan akceptacji)?0q0 q1

  • Jeśli wprowadzona zostanie , czy system przejdzie zarówno do q 1, jak i do q 2 ?1q1q2

  • Czy system przechodzi do (stan akceptacji), jeśli nie podano danych wejściowych (pusty ciąg)?q1


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


10

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

Jeśli Twój ciąg ma wartość „0”, będzie ponownie w i q 1q0q1

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”.q2q0q2q1q0q1

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ϵ0q0q1q20111ϵ00111

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


7
„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

6

q0q0q1q1

q00q0q10q01q21q1q11

0+011101


ϵϵ


-1

Próbowałem skonstruować DFA dla tego NFA

Q

σ(Q×(ϵ))P(Q)

q0=q0

FQ,F={q0}

M

alfabet - to samo

Q=P(Q)

RP(Q)

E(R)ϵrR

σ(R,a)=rRE(σ(r,a))

q0=E({q0})

F=P(Q)÷F

Niektóre obliczają na tym FSM

1. ϵq0=E({q0})={q0,q1}q1ϵ

2. 0σ({q0,q1},0)=E(σ(q0,0))E(σ(q1,0))={q0,q1}{}={q0,q1}0

{ϵ,0}L(M)

Dzięki David Richerby


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

ϵ{q0,q1}00{q0,q1}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.