Accession Number : AD0697040

Title :   TWO CHARACTERISTIZATIONS OF THE CONTEXT-SENSITIVE LANGUAGES,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Fischer,Michael J.

Report Date : SEP 1969

Pagination or Media Count : 15

Abstract : An n-dimensional bug-automation is a generalization of a finite state acceptor to n-dimensions. With each bug B, is associated the language L(B) which is the set of top rows of n-dimensional rectangular arrays accepted by B. One-dimensional bugs define trivially the regular sets. Two-dimensional bugs define precisely the context-sensitive languages, while bugs of dimension 3 or greater define all the recursively enumerable sets. Finite state acceptors with n two-way non-writing input tapes are also considered. For each such machine M, let domain (M) be the set of all strings which are the first component of some n-tuple of tapes accepted by M. For any n > or = 1, the domains of n-tape finite state acceptors are precisely the same as the languages definable by n-dimensional bugs, so as a corollary, the domains of two-tape two-way finite state acceptors are precisely the contest-sensitive languages. (Author)

Descriptors :   (*CONTEXT SENSITIVE GRAMMARS, AUTOMATA), PROGRAMMING LANGUAGES, COMPUTATIONAL LINGUISTICS, SET THEORY, THEOREMS

Subject Categories : Linguistics
      Computer Programming and Software
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE