On the transformation of two-way finite automata to unambiguous finite automata.

This paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n -state two-way deterministic finite automaton (2DFA) and an n -state two-way unambiguous finite automaton (2UFA). It is proved that a 2UFA with n states can be transformed to a UFA with fewer than 2 n ⋅ n ! states. On the other hand, for every n , there is a language recognized by an n -state 2DFA that requires a UFA with at least Ω ((2 + 1) 2 n ⋅ n − 1) = Ω (5.828 n) states. The latter result is obtained as a lower bound on the rank of a certain matrix. [ABSTRACT FROM AUTHOR]