On multi-head finite automata

Abstract

Let mn be the class of languages defined by n-head finite automata. The Boolean and Kleene closure properties of mn are investigated, and a relationship between mn and the class sets of n-tuples of tapes defined by n-tape finite automata is established. The relationships among the multi-head languages and the context-free and context-sensitive languages are investigated, and the adage, "Two heads are better than one," is generalized. Several decision properties of the multi-head languages are derived.