About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.