[35]

(a) A k-pass DFA is just like a usual DFA except that the input head reads the input k times, from the first symbol to the last symbol, moving right only during each pass. Use incompressibility to show that a k-pass DFA is exponentially more succinct than a (k − 1)-

pass DFA. In other words, for each k, there is a language Lk such that Lk can be accepted by a k-pass DFA with O(kn) states, but the smallest

(k − 1)-pass DFA accepting Lk requires Ω(2n) states.

(b) A sweeping two-way DFA is again just like a usual finite automaton except that its input head may move in two directions with the restriction that it can reverse direction only at the two ends of the input. If a sweeping two-way DFA makes k−1 reversals during its computation, we call it a k-sweep two-way DFA. Show that there is a language Rk that can be accepted by a 2k-sweep two-way DFA with p(k, n) states for some polynomial p, but the smallest (2k − 1)-sweep two-way DFA accepting Rk requires an exponential number of states in terms of k and n.

Comments. W.J. Sakoda and M. Sipser studied sweeping automata in

[Proc. 10th ACM Symp. Theory Comput., 1978, pp. 275–286]. They called the k-pass DFA by the name ‘k-component series FA.’ Source:

T. Jiang, e-mail, 1992.