Two-Way Machines and de Bruijn Words

We consider de Bruijn words and their recognition by finite automata. While on one-way nondeterministic automata the recognition of de Bruijn words of order k requires exponentially many states in k, we show a family of de Bruijn words such that the word wk of order k, for k>0, can be recognized by a deterministic two-way finite automaton with O(k3) states. Using this result we are able to obtain an exponential-size separation from deterministic two-way finite automata to equivalent context-free grammars. We also show how wk can be generated by a 1-limited automaton with O(k3) states and a constant-size work alphabet. This allows to obtain small 1-limited automata for certain unary languages and to show an exponential-size separation from unary deterministic 1-limited automata to equivalent deterministic pushdown automata.