Two-way finite automata with quantum and classical states (2qcfa’s) were introduced by Ambainis and Watrous. Though this computing model is more restricted than the usual
two-way quantum finite automata (2qfa’s) first proposed by Kondacs and Watrous, it is still more powerful than the classical counterpart. In this note, we
focus on dealing with the operation properties of 2qcfa’s. We prove that the Boolean operations (intersection, union, and
complement) and the reversal operation of the class of languages recognized by 2qcfa’s with error probabilities are closed;
also, we verify that the catenation operation of such class of languages is closed under certain restricted condition. The
numbers of states of these 2qcfa’s for the above operations are presented. Some examples are included, and
{xxR|x Î {a,b}*,#x(a)=#x(b)}\{xx^{R}|x\in \{a,b\}^{*},\#_{x}(a)=\#_{x}(b)\}
is shown to be recognized by 2qcfa with one-sided error probability, where
x
R
is the reversal of
x, and #
x
(
a) denotes the
a’s number in string
x.
This work was supported by the National Natural Science Foundation under Grant 90303024 and Grant 60573006, the Research Foundation
for the Doctorial Program of Higher School of Ministry of Education under Grant 20050558015, and Program for New Century Excellent
Talents in University (NCET) of China.