Descriptional Complexity and Operations - Two Non-Classical Cases

In the talk we study the behaviour of some complexity measures if operations (union, complement, product, star, etc.) are applied to languages. In the first part, we discuss regular languages where the number of accepting states is the considered complexity measure. In the second part, we study context-free languages and take the number of nonterminals, the number of productions, and the total number of symbols as complexity measures. Moreover, we compare the behaviour of arbitrary regular/context-free languages with that of finite languages and/or languages over unary alphabet.