CMIMC 2016 Finals Problem CS.3

Let \varepsilon denote the empty string. Given a pair of strings (A, B) \in\{0,1,2\}^{*} \times\{0,1\}^{*}, we are allowed the following operations:

\left\{\begin{array}{l} (A, 1) \rightarrow(A 0, \varepsilon) \\ (A, 10) \rightarrow(A 00, \varepsilon) \\ (A, 0 B) \rightarrow(A 0, B) \\ (A, 11 B) \rightarrow(A 01, B) \\ (A, 100 B) \rightarrow(A 0012,1 B) \\ (A, 101 B) \rightarrow(A 00122,10 B) \end{array}\right.

We perform these operations on (A, B) until we can no longer perform any of them. We then iteratively delete any instance of 20 in A and replace any instance of 21 with 1 until there are no such substrings remaining. Among all binary strings X of size 9 , how many different possible outcomes are there for this process performed on (\varepsilon, X)?