A machine realization of the linear context-free languages

Abstract

A correspondence is established between N2, the class of sets of pairs of tapes defined by nondeterministic 2-tape finite automata, and L, the class of linear context-free languages. A second correspondence, which is one-one, between N2 and a subclass of L is found. This subclass of L is then characterized by expressions quite similar to regular expressions. It is indicated how to develop analogous characterizations for other subclasses of L. A large portion of this paper appears in the author's doctoral thesis which was presented to the Division of Engineering and Applied Physics, Harvard University. The thesis research was under the supervision of Professor Patrick C. Fischer. © 1967 Academic Press Inc.