We examine the operational state complexity assuming that the operands of a regular operation are represented by nondeterministic finite automata, while the language resulting from the operation is required to be represented by a deterministic finite automaton. We get tight upper bounds $$2^n$$ for complementation, reversal, and star, $$2^m$$ for left and right quotient, $$2^{m+n}$$ for union and symmetric difference, $$2^{m+n}-2^m-2^n+2$$ for intersection, $$2^{m+n}-2^n+1$$ for difference, $$\frac{3}{4}2^{m+n}$$ for concatenation, and $$2^{mn}$$ for shuffle. We use a binary alphabet to describe witnesses for complementation, reversal, star, and left and right quotient, and a quaternary alphabet otherwise. Whenever we use a binary alphabet, it is always optimal.