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$. 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. a:l$ denotes a new list formed by adding a at the head of list $l$.
For example:
$\text{head}([0,1,0]) \: =\: 0, \text{tail}([0,1,0]) = [1,0]$,
$\text{head}([1]) \: = \: 1, \text{tail}([1]) = [ \: ],$ and
$1:[0,1,0] \: = \: [1,0,1,0]$.
Consider the following functions:
$xor$ takes takes as input two bits and returns a bit.
xor(a,b)
if (a == b) return(0)
else return(1)
endif
$f1$ takes as input a list and returns another list.
f1(s)
if (s == []) then return([1])
else if (head(s) == 0) then return(1:tail(s))
else if (head(s) == 1) then return(0:f1(tail(s)))
endif
$f2$ takes as input a bit and a list and returns a bit.
f2(b,s)
if (s == [ ]) then return(b)
else if (head(s) == 0) then return(f2(xor(b,1),tail(s)))
else if (head(s) == 1) then return(xor(b,1))
endif
$g1$ takes as input a nonnegative number and returns a list.
g1(n)
if (n == 0) then return([0])
else return f1(g1(n-1))
endif
$g2$ takes as input a nonnegative number and returns a bit.
g2(n)
if (n == 0) then return(0)
else return f2(g2(n-1),g1(n))
endif
What is the value of $g2(7)$ and $g2(8)$?
