Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States

{\it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over {\it two-way probabilistic finite automata} (2PFA) for recognizing some non-regular languages such as the language L_eq=\{aⁿbⁿmid nin mathbf{N}\} and the palindrome language L_pal=\{ωin \{a,b\}^*midω=ω^R\}, where x^R is x in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language L_m=\{xcymid Σ=\{a, b, c\}, x,yin\{a,b\}^*,cinΣ, |x|=|y|\} that is similar to the middle language L_middle=\{xaymid x,yinΣ^*,ainΣ, |x|=|y|\}. We prove that the language L_m can be recognized by 2QCFA with one-sided error in polynomial expected time. Also, we show that L_m can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus L_m is another witness of the fact that 2QCFA are more powerful than their classical counterparts.