Grammatical complexity of finite languages

Abstract

In this thesis, we will investigate finite languages which are generated by different types of context-free grammars from the points of view of descriptional and computational complexity. Specifically, we will study several aspects of the exact and cover complexity of finite languages, i.e., the minimal number of productions a grammar needs in order to generate and cover, respectively, a given finite language. From the point of view of computational complexity, we will consider the following variants of the smallest grammar problem: what is the size or number of productions of a minimal grammar that generates a given finite language? It will be shown that both the minimal size and the minimal number of productions needed in order to generate a given finite language cannot be approximated within certain factors, unless P = NP. In addition, we will also consider problems under the assumption of the so-called Exponential Time Hypothesis. Moreover, from a mere descriptional complexity point of view, we will investigate the exact and cover complexity of different language operations on finite languages. Finally, we will give a relative succinctness classification of several grammar as well as several complexity measure types based on the number of productions.