<p>First, a warning: this will involve exponential <span class="math-container">$(2^{n \log n})$</span> blowup in the number of states (see <a href="https://cstheory.stackexchange.com/questions/20107/2dfa-that-requires-many-states-in-equivalent-dfa">here</a>). However, if your application is fine with computing the states of the DFA "on the fly" then you can avoid the exponential blowup -- you will get an algorithm for the normal DFA where the state is represented using <span class="math-container">$O(n)$</span> memory.</p>

<h3>Conversion from 2DFA to DFA</h3>

<p>The basic idea is that if the 2DFA has states <span class="math-container">$Q$</span>, your DFA will have states <span class="math-container">$Q \times (Q \to Q)$</span>. The state here has two components. Suppose the input to the DFA so far is <span class="math-container">$x$</span>.</p>

<ul>
<li><p>The first component of the state <span class="math-container">$q \in Q$</span> represents the state the 2DFA will arrive in after moving to the right of <span class="math-container">$x$</span> and into the following character.</p></li>
<li><p>The second component is a function <span class="math-container">$f: Q \to Q$</span> which gives a table of what will happen if the 2DFA comes <em>back</em> into <span class="math-container">$x$</span> later: suppose the 2DFA moves to the left into <span class="math-container">$x$</span> and transitions into state <span class="math-container">$p$</span>. Then some internal things will happen, but eventually the 2DFA will move back to the right out of <span class="math-container">$x$</span> (or it will terminate and accept, if your representation of 2DFAs allows it).</p></li>
</ul>

<p>Then the transition function of the DFA needs to update both the current state and the table. Updating the table can be done by simulating the execution of the 2DFA on input <span class="math-container">$xa$</span>, where <span class="math-container">$a$</span> is some additional character, and the head of the 2DFA starts on <span class="math-container">$a$</span>, with the following modifications. When the 2DFA travels into input <span class="math-container">$x$</span>, just use the table to determine where it will end up when it comes out. And if it travels to the right of <span class="math-container">$a$</span>, then just stop simulating because this gives the result of the table.</p>

<h3>Dealing with nontermination</h3>

<p>Some 2DFAs do not terminate. This is a problem for the above conversion because you might end up simulating the 2DFA forever when trying to update the table. Some ways to fix this:</p>

<ol>
<li><p>Ensure the 2DFA always terminates on every input before converting it, by detecting and removing loops.</p></li>
<li><p>Add "infinite loop" as a possible state of your DFA. When updating the table, detect the set of "visited" states so far and, if you find that you repeat a visited state, declare the result to be an infinite loop.</p></li>
<li><p>Same as (2), but instead of having a set of visited states, just upper bound the simulation by a <span class="math-container">$n$</span> (the number of states), as after <span class="math-container">$n$</span> steps you know that it will not terminate.</p></li>
</ol>

<p>Of these, (1) is probably the hardest (unless you already know the 2DFAs you have always terminate due to your application domain), and (3) is probably the easiest. I will use (3) below.</p>

<h3>On-the-fly algorithm</h3>

<p>Putting these ideas together into an "on-the-fly" algorithm to execute the DFA, here is some rough pseudocode.</p>

<pre><code>Input: a 2DFA A with states Q

Assume that Q includes special states Accept, Reject, and Loop (if not, add them).
Assume that the input has start and end markers &lt; and &gt;.

Here we convert to a 1DFA where the state has type
    State = Q x (Q -&gt; Q).

// Calculate the initial state of the DFA
function initial(A: 2DFA) -&gt; State:
    q = initial state of A
    table = identity map: contains key q, value q for all q in Q
    // Read in start-of-input character
    return update(A, (q, table), '&lt;')

// Update the state of the DFA
function update(A: 2DFA, (q, table): State, a: char) -&gt; State:
    // first create the new table, table'
    for each q in Q:
        find the transition of A from state q on input a.
        while it moves left, apply the table and repeat, up to n times (where n is the size of Q), until it moves right.
        - Case 1: If it doesn't move right after n steps, set table'[q] = Loop.
        - Case 2: If it eventually moves right and transitions to state r, then set table'[q] = r.

    // Now update the state -- this is just the value already calculated in the table
    q' = table'[q]

    return (q', table')

// check if the DFA accepts or rejects
function is_accepting(A: 2DFA, (q, table): State) -&gt; Boolean:
    // Read in final character
    q', table' = update(A, (q, table), '&gt;')
    return true if q' == Accept, false otherwise
</code></pre>

CC BY-SA 4.0
2020-04-26T08:43:44.567Z
Very satisfying explanation sir thank you so much ! I wil try to implement that and i will share the code on github.
Karl Millson
CC BY-SA 4.0
2020-04-25T13:39:32.303Z
2020-04-25T13:45:24.827Z
2020-04-25T13:45:24.827Z
Caleb Stanford
<p>Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly,  it is a standard argument and the algrothim follows clearly from the proof. The chapter can be found at the following link.  <a href="https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22" rel="noreferrer">https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22</a></p>

CC BY-SA 4.0
2020-04-25T13:28:59.577Z
2020-04-25T13:28:59.577Z
Taylor Dohmen
<p>How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ? 
I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in Java.</p>

CC BY-SA 4.0
2020-04-22T22:52:40.747Z
If you plan to implement it, I would potentially be interested in helping (assuming that this is not a homework assignment).  Please let me know if you make the repo public.  Thank you!
Michael Wehar
CC BY-SA 4.0
2020-04-22T23:03:53.243Z
@MichaelWehar Thank you for your attention. This is not a homework and i am not a student. Sure ! I am supporting to open source software. I can gladly share all code on github as public.
Karl Millson
CC BY-SA 4.0
2020-04-23T01:39:44.913Z
That's awesome!  Please do share the repo once you're ready.  It sounds like a really neat project.  :)
Michael Wehar
CC BY-SA 4.0
2020-04-23T12:40:45.210Z
Share here please!
Aryeh
CC BY-SA 4.0
2020-04-23T18:17:46.247Z
Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly,  it is a standard argument and the algrothim follows clearly from the proof. The chapter can be found at the following link.  https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22
Taylor Dohmen
CC BY-SA 4.0
2020-04-25T08:46:48.453Z
@Taylor Dohmen please consider converting your comment into an answer, I doubt there is a more explicit description out there...
Hermann Gruber
<fl.formal-languages><automata-theory><regular-language><dfa>
2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata
Karl Millson
# 2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

(Asked by: username_0 on 2020-04-22)

How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ?
I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in Java.

**Tags:** fl.formal-languages, automata-theory, regular-language, dfa

> **Comments:**
> **username_1**: If you plan to implement it, I would potentially be interested in helping (assuming that this is not a homework assignment).  Please let me know if you make the repo public.  Thank you!  
> **username_0**: @MichaelWehar Thank you for your attention. This is not a homework and i am not a student. Sure ! I am supporting to open source software. I can gladly share all code on github as public.  
> **username_1**: That's awesome!  Please do share the repo once you're ready.  It sounds like a really neat project.  :)  
> **username_2**: Share here please!  
> **username_3**: Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly,  it is a standard argument and the algrothim follows clearly from the proof. The chapter can be found at the following link.  https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22  
> **username_4**: @username_3 please consider converting your comment into an answer, I doubt there is a more explicit description out there...  

---

## 2 answers

### Answer by username_5 on 2020-04-25. Score: 4 | Accepted answer

First, a warning: this will involve exponential $(2^{n \log n})$ blowup in the number of states (see here). However, if your application is fine with computing the states of the DFA "on the fly" then you can avoid the exponential blowup -- you will get an algorithm for the normal DFA where the state is represented using $O(n)$ memory.
Conversion from 2DFA to DFA
The basic idea is that if the 2DFA has states $Q$, your DFA will have states $Q \times (Q \to Q)$. The state here has two components. Suppose the input to the DFA so far is $x$.

The first component of the state $q \in Q$ represents the state the 2DFA will arrive in after moving to the right of $x$ and into the following character.
The second component is a function $f: Q \to Q$ which gives a table of what will happen if the 2DFA comes back into $x$ later: suppose the 2DFA moves to the left into $x$ and transitions into state $p$. Then some internal things will happen, but eventually the 2DFA will move back to the right out of $x$ (or it will terminate and accept, if your representation of 2DFAs allows it).

Then the transition function of the DFA needs to update both the current state and the table. Updating the table can be done by simulating the execution of the 2DFA on input $xa$, where $a$ is some additional character, and the head of the 2DFA starts on $a$, with the following modifications. When the 2DFA travels into input $x$, just use the table to determine where it will end up when it comes out. And if it travels to the right of $a$, then just stop simulating because this gives the result of the table.
Dealing with nontermination
Some 2DFAs do not terminate. This is a problem for the above conversion because you might end up simulating the 2DFA forever when trying to update the table. Some ways to fix this:

Ensure the 2DFA always terminates on every input before converting it, by detecting and removing loops.
Add "infinite loop" as a possible state of your DFA. When updating the table, detect the set of "visited" states so far and, if you find that you repeat a visited state, declare the result to be an infinite loop.
Same as (2), but instead of having a set of visited states, just upper bound the simulation by a $n$ (the number of states), as after $n$ steps you know that it will not terminate.

Of these, (1) is probably the hardest (unless you already know the 2DFAs you have always terminate due to your application domain), and (3) is probably the easiest. I will use (3) below.
On-the-fly algorithm
Putting these ideas together into an "on-the-fly" algorithm to execute the DFA, here is some rough pseudocode.
Input: a 2DFA A with states Q

Assume that Q includes special states Accept, Reject, and Loop (if not, add them).
Assume that the input has start and end markers < and >.

Here we convert to a 1DFA where the state has type
    State = Q x (Q -> Q).

// Calculate the initial state of the DFA
function initial(A: 2DFA) -> State:
    q = initial state of A
    table = identity map: contains key q, value q for all q in Q
    // Read in start-of-input character
    return update(A, (q, table), '<')

// Update the state of the DFA
function update(A: 2DFA, (q, table): State, a: char) -> State:
    // first create the new table, table'
    for each q in Q:
        find the transition of A from state q on input a.
        while it moves left, apply the table and repeat, up to n times (where n is the size of Q), until it moves right.
        - Case 1: If it doesn't move right after n steps, set table'[q] = Loop.
        - Case 2: If it eventually moves right and transitions to state r, then set table'[q] = r.

    // Now update the state -- this is just the value already calculated in the table
    q' = table'[q]

    return (q', table')

// check if the DFA accepts or rejects
function is_accepting(A: 2DFA, (q, table): State) -> Boolean:
    // Read in final character
    q', table' = update(A, (q, table), '>')
    return true if q' == Accept, false otherwise

> **Comments:**
> **username_0**: Very satisfying explanation sir thank you so much ! I wil try to implement that and i will share the code on github.  

---

### Answer by username_3 on 2020-04-25. Score: 5

Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly, it is a standard argument and the algrothim follows clearly from the proof. The chapter can be found at the following link. <https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22>


---

