Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations

The success of large language models (LLMs) has motivated formal theories of language generation and learning. We study the framework of language generation in the limit, where an adversary enumerates strings from an unknown language K drawn from a countable class, and an algorithm must generate unseen strings from K. Prior work showed that generation is always possible, and that some algorithms achieve positive lower density, revealing a validity--breadth trade-off between correctness and coverage. We resolve a main open question in this line, proving a tight bound of 1/2 on the best achievable lower density. We then strengthen the model to allow partial enumeration, where the adversary reveals only an infinite subset C subseteq K. We show that generation in the limit remains achievable, and if C has lower density α in K, the algorithm's output achieves density at least α/2, matching the upper bound. This generalizes the 1/2 bound to the partial-information setting, where the generator must recover within a factor 1/2 of the revealed subset's density. We further revisit the classical Gold--Angluin model of language identification under partial enumeration. We characterize when identification in the limit is possible -- when hypotheses Mt eventually satisfy C subseteq M subseteq K -- and in the process give a new topological formulation of Angluin's characterization, showing that her condition is precisely equivalent to an appropriate topological space having the TD separation property.