We consider the state complexity of basic operations on non-returning regular languages. For a non-returning minimal DFA, the start state does not have any in-transitions. We establish the precise state complexity of four Boolean operations (union, intersection, difference, symmetric difference), catenation, reverse, and Kleene-star for non-returning regular languages. Our results are usually smaller than the state complexities for general regular languages and larger than the state complexities for suffix-free regular languages. In the case of catenation and reversal, we define witness languages over a ternary alphabet. Then we provide lower bounds for a binary alphabet. For every operation, we also study the unary case.

The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2 m+n−1 −2 m−1 −2 n−1 +1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as 3/4 2 mn for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu (“State complexity of combined operations”, Theoret. Comput. Sci., 383 (2007) 140–152).