Obtaining tight upper-bounds for the state complexities of DFA operations
Sheng Yü, Qingyu Zhuang, Kai Salomaa · 2003
The authors consider the state complexity of basic operations of regular languages. They show that the number of states that is sufficient and necessary in the worst case for a deterministic finite automaton (DFA) to accept the catenation of an m-state DFA language and an n-state DFA language is exactly m2/sup n/-2/sup n-1/, for m, n>1. The result of 2/sup n-1/+2/sup n-2/ states is obtained for the star of an n-state DFA language, n>1. State complexities for other basic operations and for regular languages over a one-letter alphabet are also studied.>