Yes, the problem is decidable. 

First note that in $B_n$ everything is forgotten after $n$ steps.

Now consider a graph $H = (V', A')$ where every vertex corresponds to a subset of $V$. We put an edge in colour $c$ from $u'$ to $v'$ if every vertex in $u'$ has an edge in colour $c$ to a vertex in $v'$. Now consider the following question:

Does there exist an subgraph of $H$ on the same set of vertices such that every vertex has exactly one outgoing edge in each colour such that all recurrent vertices correspond to single element subsets in $V$?

If there exists a homomorphism such a subgraph exists. For every starting vertex of $H$ and every string of length $n$ there exists a path following that string ending in a vertex corresponding to a single element subset in $V$ (by the property of forgetting everything after $n$ steps). For every $u' \in V'$ we define $g(u')$ to be

$$g(u') = \begin{cases} 0 & \text{if } |u'| = 1\\ \max\left(\min_{\delta^+_0(u')}, \min_{\delta^+_1(u')}\right) & \text{otherwise,}\end{cases}$$
where $\delta^+_c(u')$ denotes all vertices $v'$ such that there exists an edge from $u'$ to $v'$ in colour $c$. For each $u' \in V'$ we pick one outgoing edge of each colour minimizing the value $g(v')$ of the target vertex $v'$.

Now suppose conversely that such a subgraph exists and additionally assume there exists an all-zero-tree from every vertex to a specific vertex, which we will call $v_0$ and similarly a vertex $v_1$ (this is another necessary and decidable condition for a homomorphism). Then there exist such a subgraph where $0^{\max g(u')}$ always leads to $v_0$ and $1^{\max g(u')}$ to $v_1$.

By considering the path starting at the vertex $V \in V'$, we can observe that this corresponds to an algorithm forget the current state in $m = \max g(u') \leq 2^{|V|}$ steps. The problem is that if two strings become equal they have to start this memory wiping process at the same time.

We need to ensure that $f$ is surjective. We can do this by constructing a path starting at $v_0$ which visits all edges and taking its corresponding string $s$. 

Now we need to synchronize the memory erasure.

When the a string doesn't start with $0^{n - |s|}$ we want to erase its memory at some point. If a certain pattern $p$ of length at most $m$ appears $3m$ times at the end, i.e. there is a suffix $p^{3m}$ with $|p| \leq m$, then we try to reach a vertex such that there is a cycle $p$ starting and ending there. If there are multiple such $p$ pick the longest which is not a power itself.

If no such pattern $p$ exists start the memory erasure when the length $2m$ suffix is the lexicographically largest substring of itself

Therefore the conditions to check are:
- There is a vertex in $G$ which is reachable from every other vertex using only 0-edges.
- There is a vertex in $G$ which is reachable from every other vertex using only 1-edges.
- $H$ has such a subgraph. (You can start with the single-vertex subsets and add other subsets one by one if they have a 0-edge and a 1-edge to existing subsets.)
- $G$ is strongly connected.