p<1 $ if any yes-instance (resp. no-instance) is accepted (resp. rejected) with probability $ p' \geq p $ and the answer of “don’t know” is given with the remaining probability $ 1 - p' $. If $ \mathtt{P_{yes}} \cup \mathtt{P_{no}} = \Sigma^* $, then it is called language recognition (for $ \tt P_{yes} $) instead of solving a promise problem.

Exact separation
================

We start with defining a new language $ {\mathtt{END}}$: $${\mathtt{END}}= \{ w \in \{0,1,2\}^*2\{0,1,2\}^* \mid w^r[{|w|_2}] = 1 \},$$ where $ |w|_2 $ is the number of symbols $2$ in $ w $, $ w^r $ is the reverse of $w$, and $ w^r[{|w|_2}] $ is the $ (|w|_2) $-th symbol of $ w^r $.

The language $ {\mathtt{END}}$ is recognized by an AfCA $ A $ exactly.

We will use two states $ (s_1,s_2) $ for deterministic computation and five states ($ p_0,p_1,p_2,p_3,p_4 $) for affine computation. The initial states are $ s_1 $ and $p_0 $. In other words, we consider a product of a 2-state deterministic finite automaton and a 5-state affine counter automaton.

The classical part is responsible for checking whether the given input has at least one symbol 2. For this purpose, 