Affiliations: Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7, [email protected] | Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7, [email protected]
Note: [] Address for correspondence: Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7
Abstract: In this paper, we study the state complexities of four combined operations: L*1 ∪ L2, L*1 ∩ L2, LR1 ∪ L2, and LR1 ∩ L2. 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.
Keywords: state complexity, combined operations, regular languages, finite automata
