Accession Number:

AD0602071

Title:

LANGUAGE IDENTIFICATION IN THE LIMIT,

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CALIF

Personal Author(s):

Report Date:

1964-07-01

Pagination or Media Count:

36.0

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

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE