Two-way finite automaton: How does the automaton remember the state

Question

I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Σ, δ, q1, F). the 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#}, δ|, q0, {qF}) and a following language
L = { #u# | uu ∈ L(A)}.

In following paragraph I will describe how would it works, if we are reading a word that belongs to the language.

In the first procedure automaton B follows the states of automaton A, when it reach right '#', it stops, remember the accepting state and starts to move back through the copied states of automaton A: Q| as long as it come to right '#'. Afterwards it starts moving on through the copied states Q|| of automaton A, and once it reaches out the right '#' checks if it is the saved accepting state. Image below shows the movements where qN is a failing/non-accepting state and +1 movement of head to right and -1 movement of the head to left.

Question

How does the 2-DFA remember that it reached out during first walk through the states of automaton A the accepting state for the second walk?

Answer 1

Here is a simpler example, for NFAs.

We will show that if $L_1,L_2$ are regular languages over disjoint alphabets $\Sigma_1,\Sigma_2$, then so is the following language over $\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 \}. $$ Here is the idea. Start with DFAs $A_1,A_2$ for $L_1,L_2$. We will construct a DFA for $L$ which acts as follows. It starts by simulating $A_1$. When it encounters a symbol from $\Sigma_2$, it remembers the state that $A_1$ is in, and switches to $A_2$. When it encounters a symbol from $\Sigma_1$, it switches back to $A_1$, assuming that $A_2$ is at an accepting state. It goes to a failure state if it encounters a letter from $\Sigma_2$ again.

Here are the details, showing how we implement remembering the state of $A_1$.

Let $A_1 = \langle Q_1,\Sigma_1,q_{01},\delta_1,F_1 \rangle$ and let $A_2 = \langle Q_2,\Sigma_2,q_{02},\delta_2,F_2 \rangle$. We construct a new DFA $A = \langle Q,\Sigma,q_0,\delta,F \rangle$ as follows:

• The set of states is $Q = (Q_1 \times \{1\}) \cup (Q_1 \times Q_2) \cup (Q_1 \times \{2\}) \cup \{q_f\}$. States in the first part will be used to simulate $A_1$ before a symbol from $\Sigma_2$ is ever encountered. States in the second part will be used to simulate $A_2$ while remembering the state of $A_1$. States in the third part will be used to simulate $A_1$ after reading the $y$ part. The final state will handle various modes of failure.

• The initial state is $(q_{01},1)$.

• The transition function is defined as follows:

  • If $\sigma \in \Sigma_1$ then $\delta((q,1),\sigma) = (\delta_1(q,\sigma),1)$: we just advance $A_1$.
  • If $\sigma \in \Sigma_2$ then $\delta((q,1),\sigma) = (q,\delta_2(q_{02},\sigma))$: we remember the state of $A_1$, and advance $A_2$.
  • If $\sigma \in \Sigma_2$ then $\delta((q_1,q_2),\sigma) = (q_1,\delta_2(q_2,\sigma))$: we advance $A_2$, while keeping the state of $A_1$ intact.
  • If $\sigma \in \Sigma_1$ and $q_2 \notin F_2$ then $\delta((q_1,q_2),\sigma) = q_f$: the $y$ part is not in $L_2$, so we signal failure.
  • If $\sigma \in \Sigma_1$ and $q_2 \in F_2$ then $\delta((q_1,q_2),\sigma) = (\delta_1(q_1,\sigma),2)$: we go back to simulating $A_1$.
  • If $\sigma \in \Sigma_1$ then $\delta((q_1,2),\sigma) = (\delta_1(q_1,\sigma),2)$: we just advance $A_1$.
  • If $\sigma \in \Sigma_2$ then $\delta((q_1,2),\sigma) = q_f$: the input is malformed, so we signal failure.
  • For all $\sigma$, $\delta(q_f,\sigma) = q_f$.
• The final states are $(F_1 \times \{1\}) \cup (F_1 \times F_2) \cup (F_1 \times \{2\})$. The first part handles the case $y=z=\epsilon$, the second handles the case $y\neq\epsilon$ and $z=\epsilon$, the third handles the case $y,z \neq \epsilon$.

Hopefully this explains how a DFA can commit a piece of information to memory. Since a DFA has only finitely many states, it can only store a constant amount of information.