2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

Question

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.

Answer 1

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:

1. Ensure the 2DFA always terminates on every input before converting it, by detecting and removing loops.

2. 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.

3. 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

Answer 2

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