On Multi-Head Finite Automata

Abstract

Let M <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf> be the class of languages defined by n-head finite automata. The Boolean and Kleene closure properties of M <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf> are investigated, and a relationship between M <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf> and the class of sets of n-tuples of tapes defined by n-tape finite automata is established. It is shown that the classes M <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> form a hierarchy; and that, moreover, for all n, there is a context-free language (CFL) in M <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n+1</inf> −M <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf> . It is further shown that there is a CFL which is in no M <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf> for any integer n. Finally, several decision properties of the multi-head languages are established.