State Complexity of Combined Operations with Union,Intersection,Star and Reversal

Abstract

In this paper, we study the state complexities of four combined operations: L^*₁ ∪ L₂, L^*₁ ∩ L₂, L^R₁ ∪ L₂, and L^R₁ ∩ L₂. The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are different from the mathematical compositions of the state complexities of their individual participating operations.