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.

Movement of the 2-DFA

enter image description here


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?

  • $\begingroup$ When we say that an automaton remembers something, we mean that this information is stored in the current state. We can think of a state as a structure, one field of which is this something that we need to remember. $\endgroup$ – Yuval Filmus May 15 '20 at 11:23
  • $\begingroup$ This comes up also when discussing DFAs or NFAs, so before writing this as a full-fledged answer, I wanted to make sure that the issue here is not specifically about 2DFAs. $\endgroup$ – Yuval Filmus May 15 '20 at 11:24
  • $\begingroup$ Thank you @YuvalFilmus for the respond, I really appreciate it. But as you said it is stored in the current state. I will attach another picture simulating movement of the 2-DFA. During the lecture was said that when we enter the accepting state for the first time, we store that information for second simulation of states of automaton A. As you said we store the information in current state, but that is what confuses me, because, the state will be changed, when the head of 2-DFA moves to the start for second movement. $\endgroup$ – michal.kyjovsky May 15 '20 at 14:27
  • $\begingroup$ The state will have to keep track of both pieces of information in parallel. Think how you can accomplish that. $\endgroup$ – Yuval Filmus May 15 '20 at 14:30
  • $\begingroup$ Don't we increase the expression power of the automaton then, if we allow to store such information in the state? $\endgroup$ – michal.kyjovsky May 15 '20 at 14:40

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.