ON THE UNRECOGNIZABILITY OF SETS.
Abstract
Many of the results achieved concerning regularity or non-regularity of sets have been done in the context of equivalence relations of finite index and a fundamental lemma concerning the way certain input can be separated. Recently Marvin Minsky and Seymour Papert developed a set of criteria for non-regularity based on a limiting quantity which seems intuitively to represent the portion or percentage of strings that are in the regular set. In this paper we define for regular sets, in terms of natural Markov processes, another quantity, p(A), which, generally speaking, again represents a kind of percentage of strings in the regular set and show that, when Minsky's limits exist, these two quantities agree. From the quantity developed in this paper, however, more information can be gathered concerning the machine which recognizes the regular set (and hence information about the regular set itself) than can be gathered from Minsky's criteria. Also described is a special machine which gives an upper bound for the growth rate of sets recognizable by a certain type of automaton. Finally it is shown that the set of well-formed trees written as strings is not a regular set. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1969
- Accession Number
- AD0703654
Entities
People
- Ronald Barry Knode
Organizations
- Naval Postgraduate School