Accession Number : AD0702963

Title :   A SOLUTION OF THE SYNTACTICAL INDUCTION-INFERENCE PROBLEM FOR A NON-TRIVIAL SUBSET OF CONTEXT-FREE LANGUAGE.

Descriptive Note : Interim technical rept.,

Corporate Author : PENNSYLVANIA UNIV PHILADELPHIA MOORE SCHOOL OF ELECTRICAL ENGINEERING

Personal Author(s) : Pao,Tsyh-Wen Lee

Report Date : AUG 1969

Pagination or Media Count : 130

Abstract : The inference problem is formulated in the form of the following questions: (1) Suppose that one is given a certain finite subset X of sample sentences in a language L, and some cues C (if necessary) and that one is allowed to test whether a certain finite number of strings yi are contained in L. Is it possible to construct a grammar of the language L from this much information. (2) How does one choose X, C and yi in order that the problem in (1) be solvable. (3) If the problem (1) can be solved, can one have an algorithm for the construction of L. This problem is considered in the case of finite state languages. The method of solving the problem for finite state languages is then extended to a non-trivial subclass of context-free languages, which are called delimited languages. (Author)

Descriptors :   (*CONTEXT FREE GRAMMARS, *SYNTAX), SET THEORY, ALGORITHMS, THESES

Subject Categories : Linguistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE