Wie verwendet eine NFA Epsilon-Übergänge?

12

Im Bild unten versuche ich herauszufinden, was genau diese NFA akzeptiert.

Bildbeschreibung hier eingeben

Was mich verwirrt, ist der Sprung bei .ϵq0

  • Wenn eine eingegeben wird, wechselt das System dann zu und (dem Akzeptanzstatus)?0q0 q1

  • Wenn eine eingegeben wird, wechselt das System zu und ?1q1q2

  • Geht das System nur dann nach (Accept State), wenn keine Eingabe erfolgt (leere Zeichenkette)?q1

user3472798
quelle
2
Gehen Sie zurück zu den Definitionen: Eine NFA akzeptiert ein Wort, wenn eine Berechnung darauf akzeptiert. NFAs sind an sich keine "Algorithmen" im Sinne von DFA.
Raphael

Antworten:

9

Jedes Mal, wenn Sie sich in einem Zustand mit einem Übergang befinden, bedeutet dies, dass Sie sich automatisch in BEIDEN Zuständen befinden, um dies für Sie zu vereinfachen:ϵ

Wenn der String ist, enden Ihre Automaten beide mit q 0 und q 1ϵq0q1

Wenn Ihre Zeichenfolge "0" ist, wird es wieder in und Q 1 seinq0q1

Wenn Ihre Zeichenfolge '1' ist, ist sie nur in , denn wenn Sie vom Punkt von q 0 aus schauen , haben Sie einen Übergang von '1' zu q 2 , aber Sie müssen auch prüfen , ob Sie es sind in q 1 (wenn du in q 0 warst, warst du auch immer in q 1 ) gibt es keinen '1'-Übergang, so dass dieser alternative Pfad einfach "stirbt".q2q0q2q1q0q1

Nur durch die in diesen Fällen sucht seine leicht zu sehen , dass Ihre Automaten akzeptiert , 0 * , und gehen von q 0 bis q 1 , der einzige Weg , um zu erreichen q 2 ist 0 * 11 * 1 , so, diese wieder Ihre Automaten ε , 0 , 0 11 1ϵ0q0q1q20111ϵ00111

Hoffe das hat dir geholfen, wenn du weitere Zweifel hast, frag einfach!

H_DANILO
quelle
7
"es bedeutet, dass Sie sich automatisch in BEIDEN Staaten befinden" - ich denke nicht, dass dies eine hilfreiche Intuition ist, dh, sie repräsentiert den Nicht-Determinismus in falscher Weise.
Raphael
Warum stellt es es falsch dar? Nun, durch die Definition des Deltas über Nichtdeterminismus erhalten Sie eine Menge von Zuständen anstatt nur 1 korrekt? Dies kann nur bedeuten, dass Sie sich in beiden Staaten befinden.
H_DANILO
Es fördert die Idee, dass nicht deterministische Maschinen "alle Lösungen parallel versuchen". Das passiert algorithmisch nicht. Der Nichtdeterminismus ist ein deskriptiver Formalismus, keine algorithmische Technik.
Raphael
Ich habe versucht, es auf verständliche Weise
auszudrücken
@Raphael Was wäre Ihrer Meinung nach eine hilfreichere Intuition?
Andrey Portnoy
5

Im Zustand ohne jegliche Eingabe die NFA liest beiden Aufenthalte in q 0 und (in einem alternativen Universum, wenn man so will) es auch bewegt in dem Zustand q 1 . Dies ähnelt dem, was in einer NFA passieren würde, die bei der Eingabe eines Zeichens zwei Übergänge in verschiedene Zustände hatte. Insbesondere akzeptiert Ihr NFA den leeren String, da er bei keiner Eingabe in den Akzeptanzzustand q 1 übergehen kann .q0q0q1q1

Wenn Sie Ihr Beispiel fortsetzen und den Zustand als Eingang 0 betrachten , wird dieses Symbol verbraucht, der Zustand q 0 (die Schleife) wird beibehalten und es wird auch der Zustand q 1 angenommen , wodurch der Eingang 0 akzeptiert wird . Im Zustand q 0 , in dem Eingang 1 gelesen wird , würde der NFA in den Zustand q 2 übergehen . Es könnte auch sein, dass es die 1 nicht verbraucht , in einem anderen Universum in den Zustand q 1 wechselt und dort hängen bleibt (und nicht akzeptiert, da es nicht alle Eingaben gelesen hat), da es keinen Übergang von q 1 auf eine 1 gibt .q00q0q10q01q21q1q11

Sehen Sie, wenn Sie sich selbst davon überzeugen kann , dass die Sprache , die von dieser Maschine angenommen durch den regulären Ausdruck bezeichnet , das heißt, eine beliebige Zeichenfolge aus null oder mehr 0 entweder durch nichts gefolgt s an allen oder zwei oder mehr 1 s.0+011101


Übrigens gibt es einen Algorithmus, der eine NFA mit Bewegungen verwendet und eine äquivalente NFA ohne ϵ- Bewegungen erzeugt, die Sie vermutlich in Kürze lernen werden.ϵϵ

Rick Decker
quelle
-1

Ich habe versucht, DFA für diese NFA zu konstruieren

- Alphabet gesetzt

-Zustände eingestelltQ

-Zustandsfunkσ(Q×(ϵ))P(Q)

q0=q0

FQ,F={q0}

Weil jeder NFA den gleichen DFA hat, kann DFA für diesen gegebenen NFA konstruiert werden .M

Alphabet - das gleiche

- ZuständeQ=P(Q)

Aktueller Zustand ist RP(Q)

- Epsilon-Closure-Return-Satz von Zuständen, die über null oder mehr ϵ -Verbindungen für jedes r R erreichbar sindE(R)ϵrR

-Übergängeσ(R,a)=rRE(σ(r,a))

q0=E({q0})

F=P(Q)÷F

Einige rechnen auf diesem FSM

ϵ bei Eingabe: q 0 = E ( { q 0 } ) = { q 0 , q 1 } Anfangszustand beinhaltet q 1, so dass FSM ϵ akzeptiert1. ϵ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)

Vielen Dank an David Richerby

OrangeFish
quelle
Danke, dass Sie sich bei mir bedankt haben, aber ich verstehe nicht wirklich, wie dies die Frage beantwortet. Sie haben nicht festgestellt, welche Sprache die Maschine akzeptiert, und Sie haben keine der drei Fragen beantwortet.
David Richerby
ϵ{q0,q1}00{q0,q1}