Computing the number of strings of given length contained in a language is related to classical problems of combinatorics, formal languages and computational complexity. Here we study the complexity of this problem in the case of context-free languages. It is shown that, for unambiguous context-free languages such a computation is "easy" and can be carried out by efficient parallel algorithms. On the contrary, for some context-free languages of ambiguity degree two, the problem becomes intractable. These results are related to other classical subjects concerning counting problems, exponential time recognizable languages and sparse sets.
The computational complexity of variants of computing the number of strings of given length in context-free languages is investigated by Bertoni et al. REF .
The complexity of computing the number of strings of given length in context-free languages
Theor. Comput. Sci.
Theor. Comput. Sci.
Mathematics Computer Science