432 views
1 votes
1 votes

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], . . . .
[ ] denotes the empty list, and [b] is the list consisting of one bit b. The function $length(l)$ returns the length (number of bits) in the list $l$. For a nonempty list $l$, $head(l)$ returns the first element of l, and tail(l) returns the list obtained by removing the first element from l. The operator ++ denotes list concatenation.
For example:

  • head([0,1,0]) = 0, tail([0,1,0]) = [1,0],
  • head([1]) = 1, tail([1]) = [ ], and
  • [0,1,0]++[1] = [0,1,0,1].

Consider the following functions:
$op$ takes as input two bits and returns a bit.

op(a,b)
if (a = b) return(0)
else return(1)
endif

$mystery1$ 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

$mystery2$ 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
  1. What is the value of $length(mystery2(s,t))$ in terms of $length(s)$ and $length(t)$?

Please log in or register to answer this question.

Related questions

11 votes
11 votes
2 answers
2
go_editor asked May 27, 2016
1,049 views
Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers.If a language $L$ is accepted by an NFA with $n$ sta...
18 votes
18 votes
6 answers
3