Inductive Inference of Context-free Languages Based on Context-free Expressions

Takashi Yokomori*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)115-140
Number of pages26
JournalInternational Journal of Computer Mathematics
Issue number2
Publication statusPublished - 1988 Jan 1
Externally publishedYes


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

ASJC Scopus subject areas

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Inductive Inference of Context-free Languages Based on Context-free Expressions'. Together they form a unique fingerprint.

Cite this