On the Sample Complexity of Language Generation in the Limit with Noise, Prompts, and Feedback

Language generation in the limit is a learning paradigm in which a learner observes an infinite stream of strings from an unknown target language, chosen from a countable collection, and must eventually produce strings not yet seen. This task is always tractable, i.e., for any countable collection, there exists a learner that eventually succeeds. A natural follow-up question is: how many examples does the learner need before it can do so? Previous work established upper and lower bounds for regular, locally threshold testable (LTT), and context-free languages. However, the sample complexity has not been studied under the extensions of the framework that model noisy input, conditioning on a prefix, and feedback. In this paper, we analyze the sample complexity of language generation in each of these settings. First, we study the sample complexity for partially-ordered (PO) languages, a class not previously analyzed in this framework, and we establish exponential upper and lower bounds. Next, we show that for context-free languages, the sample bounds remain uncomputable in every setting. Finally, we show that for regular, LTT, and PO languages, finite noise increases the sample complexity by only a linear additive term, prompting generally leaves the bounds unchanged, and finite feedback can sometimes reduce them exponentially.