A SOLUTION OF THE SYNTACTICAL INDUCTION-INFERENCE PROBLEM FOR A NON-TRIVIAL SUBSET OF CONTEXT-FREE LANGUAGE.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1969
- Accession Number
- AD0702963
Entities
People
- Tsyh-wen Lee Pao
Organizations
- University of Pennsylvania