Inductive inference of context-free languages based on context-free expressions

Abstract

An inductive inference problem of context-free languages is considered. There have been many attempts to this problem, and most of them are based on a problem setup in which a representation space for hypotheses is a class of context-free grammars. An inference algorithm given in this paper, on the contrary, employs a kind of extensions of regular expressions called context-free expressions as a representation space for context-free languages. The algorithm, based on the notion of an identification in the limit, is significantly concise when compared with existing algorithms.

Then, a subclass of context-free languages is examined, and a simpler algorithm for the subclass is presented.

Further, a topic on meta inductive inference is briefly discussed.

Keywords:

• Inductive inference algorithm
• context-free language
• context-free expression
• meta inference

C.R. Categories:

• F.4.3
• I.2.6