Enumeration of Context-Free Languages and Related Structures
Michael Domaratzki, Alexander Okhotin, Jeffrey O. Shallit · 2007
In this paper, we consider the enumeration of context-free languages. In particular, for any reasonable descriptional complexity measure for context-free grammars, we demonstrate that the exact number of context-free languages of size $n$ is uncomputable. Nevertheless, we are able to give upper and lower bounds on the number of such languages. We also generalize our uncomputability results to a general theorem applicable to enumeration of equivalence classes or yes-instances of predicates.