Acceptance Probablity Of Classess In The Lower Chomsky Hierarchy - Michael , Hartwig (2010)
The study of the density of regular and context-free languages has attracted some attention culminating in the fact that those languages are either sparse, when the density can be bounded by a polynomial, dense otherwise. This work shows that for all regular and nonambiguous context-free languages the number of accepted words of given length.