Zwei-Wege-Finite-Automaton: Wie erinnert sich der Automaton an den Staat?

Question

Ich bin durch eine Theorie von zweiwege endlichen Automaten gegangen, und ich habe das gegebene Beispiel nicht verstanden, als es ein dfa a= (q, σ, δ, q1, f) gab. der 2-dfa b= (q ∪ q | ∪ q || ∪ {q0, qn, qf}, Σ ∪ {#}, δ | ∪ ∪ {#}, Δ |, q0, {qf}) und eine folgende Sprache
l= {# u # | uu ∈ L (a)} .

In dem folgenden Absatz beschreibe ich, wie es funktioniert, wenn wir ein Wort lesen, das zur Sprache gehört.



Prozedur Automaton B folgt den Staaten von Automaton A, wenn es rechts reicht "#", stoppt, erinnert sich an den akzeptierenden Zustand und beginnt sich durch die kopierten Zustände von Automaton A: q | solange es nach rechts kommt '#'. Anschließend beginnt es mit den kopierten Zuständen Q || von Automaton A, und sobald es die richtigen Überprüfungen reicht, wenn es der gespeicherte Annahmezustand ist. Bild unten zeigt die Bewegungen, in denen QN ein fehlerhafter / nicht akzeptierender Zustand ist, und +1 Bewegung von Kopf nach rechts und -1 und -1 Bewegung des Kopfes nach links.

Kummer

Frage

Wie erinnert sich die 2-DFA daran, dass er während des ersten Spaziergangs durch die Staaten von Automaton ein den akzeptierenden Zustand für den zweiten Spaziergang auszurechnen?

Answer 1

Hier ist ein einfacheres Beispiel für NFAS.

Wir zeigen, dass, wenn $ l_1, l_2 $ regelmäßige Sprachen über disjunkte Alphabete $ \ Sigma_1, \ Sigma_2 $ sind , dann ist also die folgende Sprache über $ \ Sigma=sigma_1 \ cup \ sigma_2 $ : $$ L={xyz: x, z \ in \ sigma_1 ^ *, y \ in \ sigma_2 ^ *, xz \ in l_1, y \ in l_2 \}. $$ Hier ist die Idee. Beginnen Sie mit DFAS $ A_1, A_2 $ für $ l_1, l_2 $ . Wir erstellen einen DFA für $ L $ , der wie folgt dient. Es beginnt mit dem Simulieren von $ A_1 $ . Wenn es auf ein Symbol von $ \ Sigma_2 $ trifft, erinnert sich der Zustand den Status, den $ A_1 $ ist in, und wechselt auf $ A_2 $ . Wenn es ein Symbol von $ \ Sigma_1 $ trifft, wechselt er zurück zu $ A_1 $ , vorausgesetzt, dass < Span-Klasse="Math-Container"> $ A_2 $ ist in einem akzeptierenden Zustand. Es geht in einen Fehlerzustand, wenn er auf einen Buchstaben von $ \ Sigma_2 $ erneut trifft.

Hier sind die Details, die zeigt, wie wir den Zustand des Zustands der $ A_1 $ $ implementieren.

let $ A_1=Langle q_1, \ Sigma_1, q_ {01}, \ delta_1, f_1 \ Rangle $ und lass $ A_2=Langle q_2, \ sigma_2, q_ {02}, \ delta_2, f_2 \ rangle $ . Wir erstellen einen neuen DFA- $ a=Langle q, \ Sigma, q_0, \ DELTA, F \ Rangle $ wie folgt:

• Der Statussatz ist $ q= (q_1 \ times \ {1 \ \}) \ cup (q_1 \ times q_2) \ cup (q_1 \ times \ { 2 \}) \ cup \ {q_f \} $ . Die Zustände des ersten Teils werden zum Simulieren von $ A_1 $ vor einem Symbol aus $ \ Sigma_2 $ jemals aufgetreten Die Zustände des zweiten Teils werden zum Simulieren von $ A_2 $ verwendet, während sich erinnert den Status der $ A_1 $ . Die Zustände im dritten Teil werden zum Simulieren von $ A_1 $ nach dem Lesen des $ y $ teil. Der endgültige Zustand verarbeitet verschiedene Fehlermodi.

• Der Anfangszustand ist $ (q_ {01}, 1) $ .

• Die Übergangsfunktion ist wie folgt definiert:

  • wenn $ \ Sigma \ in \ sigma_1 $ dann $ \ Delta ((Q, 1), \ Sigma)= (\ \ delta_1 (q, \ Sigma), 1) $ : Wir erstrecken sich nur $ A_1 $ .
  • Wenn $ \ Sigma \ in \ sigma_2 $ dann $ \ Delta ((Q, 1), \ Sigma)= (q, \ delta_2 (q_ {02}, \ Sigma)) $ : wir merken sich an den Status $ A_1 $ , und voraus $ A_2 $ .
  • Wenn $ \ Sigma \ in \ sigma_2 $ dann $ \ Delta ((Q_1, Q_2), \ Sigma)= (Q_1, \ DELTA_2 (Q_2, \ SIGMA)) $ : Wir empfehlen $ A_2 $ , während der Status der $ a_1 $ intakt.
  • Wenn $ \ Sigma \ in \ Sigma_1 $ und $ q_2 \ NOTIN F_2 $ dann $ \ DELTA ((Q_1, Q_2), \ Sigma)= q_f $ : der $ y $ Teil ist nicht In $ l_2 $ , so wählen wir den Ausfall aus.
  • wenn $ \ Sigma \ in \ Sigma_1 $ und $ q_2 \ in f_2 $ dann $ \ Delta ((Q_1, Q_2), \ Sigma)= (\ DELTA_1 (Q_1, \ SIGMA), 2) $ : Wir gehen zurück zur Simulation $ A_1 $ .
  • Wenn $ \ Sigma \ in \ sigma_1 $ dann $ \ Delta ((Q_1,2), \ Sigma)= (\ DELTA_1 (Q_1, \ SIGMA), 2) $ : Wir fahren nur $ A_1 $ .
  • Wenn $ \ Sigma \ in \ sigma_2 $ dann $ \ Delta ((Q_1,2), \ Sigma)= q_f $ : Der Eingang ist fehlerhaft, also signalisieren wir den Fehler.
  • für alle $ \ Sigma $ , $ \ DELTA (Q_F, \ Sigma)= q_f $ .
• Die letzten Zustände sind $ (f_1 \ times \ {1 \ \}) \ cup (f_1 \ times f_2) \ cup (f_1 \ times \ {2 \}) $ < / span>. Der erste Teil behandelt den Fall $ y= z=Epsilon $ , die zweite Griffe den Fall $ y \ neq \ Epsilon $ und $ z=Epsilon $ , der dritte griffe den Fall

TH-Container "> $ y, z \ neq \ epsilon $ .

Hoffentlich erklärt dies, wie ein DFA ein Informationsbild zum Erinnerung begangen kann.Da ein DFA nur endlich viele Zustände hat, kann er nur eine konstante Menge an Informationen speichern.