[edit]

# Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data

*Proceedings of 16th edition of the International Conference on Grammatical Inference*, PMLR 217:23-34, 2023.

#### Abstract

This paper is concerned with the identification in the limit from positive data of substitutable context-free languages \textsc{cfl}s) over infinite alphabets. citet{ClarkE07} showed that substitutable \textsc{cfl}s over finite alphabets are learnable in this learning paradigm. We show that substitutable \textsc{cfl}s generated by grammars whose production rules may have \emph{predicates} that represent sets of potentially infinitely many terminal symbols in a compact manner are learnable if the terminal symbol sets represented by those predicates are learnable, under a certain condition. This can be seen as a result parallel to citeauthor{ArgyrosDA2018}’s work (2018) that amplifies the query learnability of predicate classes to that of symbolic automata classes. Our result is the first that shows such amplification is possible for identifying some \textsc{cfl}s in the limit from positive data.