Show that {+, −}∗ , the set of all finite strings of pluses and minuses is enumerable by listing all its elements.

Answer 1

Strings of size 1: +, - and 2^1 = 2 is the # of elements in the set

String of size 2: ++,+-,-+,-- and 2^2 = 4 is the # of elements in the set

Strings of size 3, and there are 2^3 = 8 elements in the set

+++ -++

++- -+-

+-+ --+

+-- ---

Suppose there are 2^k elements of such strings of size k.

Appending the plus sign creates 2^k element of length k+1;

Appending the minus sign creates another 2^k elements of length k+1

So there are 2^k+2^k = 2*2^k = 2^(k+1)

which completes the proof by induction

Supp