Prove that the following algorithm generates an n-bit Gray code. A Gray code is a sequence of 2^n bit strings of length n with the Gray property: every consecutive pair of bit strings differs by one bit. (Gray codes also have the property that the first and last strings differ by one bit and every string of length n appears exactly once, but you do not need to prove either of these properties.) Input: n: number of bits in Gray code, must be a positive integer Output array gray with 2^n bit strings of length n such that every consecutive string differs by one bit 1 Algorithm: NaiveGray(n) 2 if n = 1 then 3 | return [0, 1] 4 end 5 left = right = NaiveGray(n-1) 6 Reverse right 7 Append 0 to all bit strings in left 8 Append 1 to all bit strings in right 9 return the concatenation of left and right