Context-free complexity of finite languages

AbstractIn this paper the investigation of the theory of grammatical complexity as started by Bucher (1981) and Bucher, Culik II, Maurer and Wotschke (1981) is continued. The basic question we are concerned with is the following: Given some finite language L, what is the smallest number of context-free productions needed to generate L, the so-called (context-free) complexity of L. We strengthen some of the results given by Bucher et al. (1981), the main result being a necessary condition for certain sequences of finite languages to be of sublinear complexity