
Accession Number : AD0697040
Title : TWO CHARACTERISTIZATIONS OF THE CONTEXTSENSITIVE LANGUAGES,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Fischer,Michael J.
Report Date : SEP 1969
Pagination or Media Count : 15
Abstract : An ndimensional bugautomation is a generalization of a finite state acceptor to ndimensions. With each bug B, is associated the language L(B) which is the set of top rows of ndimensional rectangular arrays accepted by B. Onedimensional bugs define trivially the regular sets. Twodimensional bugs define precisely the contextsensitive languages, while bugs of dimension 3 or greater define all the recursively enumerable sets. Finite state acceptors with n twoway nonwriting 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 ntuple of tapes accepted by M. For any n > or = 1, the domains of ntape finite state acceptors are precisely the same as the languages definable by ndimensional bugs, so as a corollary, the domains of twotape twoway finite state acceptors are precisely the contestsensitive 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