A finite sequence of bits is represented as a list with values from the set $\{0,1\}$. For example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. The function $\text{length}(l)$ returns the length (number of bits) in the list $l$. For a nonempty list $l$, $\text{head}(l)$ returns the first element of $l$, and $\text{tail}(l)$ returns the list obtained by removing the first element from $l$. The operator $++$ denotes list concatenation.
For example:
- $\text{head}([0,1,0]) = 0, \text{tail}([0,1,0]) = [1,0]$,
- $\text{head}([1]) = 1, \text{tail}([1]) = [ \: ]$, and
- $[0,1,0]++[1] = [0,1,0,1]$.
Consider the following functions:
$\text{op}$ takes as input two bits and returns a bit.
op(a,b)
if (a = b) return(0)
else return(1)
endif
$\text{mystery}1$ takes as input two lists and returns a list.
mystery1(s,t)
if (length(s) != length(t)) then return(t)
else if (length(s) = 0) then return(s)
else return([op(head(s),head(t))] ++ mystery1(tail(s),tail(t)))
endif
endif
$\text{mystery}2$ takes as input two lists and outputs a list.
mystery2(s,t)
if (length(t) = 0) then return(s)
else return( mystery1(mystery2(s,tail(t)),mystery2(s,tail(t))))
endif
Suppose $s=t=110100100$. What are the first two bits of $\text{mystery2(s,t)}$?