In Prolog

An n$-$bit Gray code is a sequence of n$-$bit strings where each binary string only differs from the previous by one bit. For example:

Gray$(1)=[\text{'}0\text{'},\text{'}1\text{'}].$

Gray$(2)=[\text{'}00\text{'},\text{'}01\text{'},\text{'}11\text{'},\text{'}10\text{'}].$

Gray$(3)=[\text{'}000\text{'},\text{'}001\text{'},\text{'}011\text{'},\text{'}010\text{'},\text{'}110\text{'},\text{'}111\text{'},\text{'}101\text{'},\text{'}100\text{'}].$

Figure out the rules to build the Gray code list and write a Prolog function called gray$($N$,$X$)$ where N if the number of bits and X is the set of strings.

For example:

gray$(1,$X$)$ should yield X $=[\text{'}0\text{'},\text{'}1\text{'}]$

gray$(2,$X$)$ should yield X $=[\text{'}00\text{'},\text{'}01\text{'},\text{'}11\text{'},\text{'}10\text{'}]$

gray$(3,$X$)$ should yield X $=[\text{'}000\text{'},\text{'}001\text{'},\text{'}011\text{'},\text{'}010\text{'},\text{'}110\text{'},\text{'}111\text{'},\text{'}101\text{'},\text{'}100\text{'}]$

gray$(4,$X$)$ should yield X $=[\text{'}0000\text{'},\text{'}0001\text{'},\text{'}0011\text{'},\text{'}0010\text{'},\text{'}0110\text{'},\text{'}0111\text{'},\text{'}0101\text{'},\text{'}0100\text{'},\text{'}1100\text{'},\text{'}1101\text{'},\text{'}1111\text{'},\text{'}1110\text{'},\text{'}1010\text{'},\text{'}1011\text{'},\text{'}1001\text{'},\text{'}1000\text{'}]$

$...$

Hints:

$(1)$ You may find the following function useful. It prefixes a list of atoms with a single character.

prefixList$(\_,[],[]).$

prefixList$($C$,[$H$|$T$],[$CH$|$Result$2])$:$-$prefixList$($C$,$T$,$Result$2),$concat$($C$,$H$,$CH$).$

Example usage:

prefixList$(\text{'}0\text{'},[\text{'}00\text{'},\text{'}01\text{'},\text{'}11\text{'},\text{'}10\text{'}],$X$)$ should yield X$=[\text{'}000\text{'},\text{'}001\text{'},\text{'}011\text{'},\text{'}010\text{'}]$

$(2)$ You may find the built$-$in reverse function useful too. For example:

reverse$([\text{'}00\text{'},\text{'}01\text{'},\text{'}11\text{'},\text{'}10\text{'}],$X$)$ should yield X$=[\text{'}10\text{'},\text{'}11\text{'},\text{'}01\text{'},\text{'}00\text{'}]$

$(3)$ Here is the base case:

gray$(1,[\text{'}0\text{'},\text{'}1\text{'}]).$