LANGUAGE IDENTIFICATION IN THE LIMIT,
Abstract
The problem considered here is that of identifying a language of some a-priori specified class. Information concerning the language may be presented by a text, an unending succession of examples of strings in the language, or by informant, a source that tells whether or not successive strings are in the language. Decision procedures are considered which generate successive guesses as to the identity of the language, which is said to be identified in the limit if these guesses are the same and correct after some finite time. Six variations of each of the two basic identification situations are considered. It was found that identification from informant is powerful enough to identify in the limit primitive recursive languages, which include contextfree languages. Use of textual information, however, is so weak that not even regular languages are limiting identifiable. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1964
- Accession Number
- AD0602071
Entities
People
- E. Mark Gold
Organizations
- RAND Corporation