State Complexity of Regular Languages

Abstract

State complexity is a descriptional complexity measure for regular languages based on the deterministic finite automaton model. We investigate and review the problems related to the state complexity of regular languages, as well as finite languages, and their operations. In particular, we compare various state complexity results for general regular languages to those for finite languages.