in Theory of Computation recategorized ago by
77 views
0 votes
0 votes

A binary string is a sequence of $0 \text{'s}$ and $1\text{'s}.$ A binary string is finite if the sequence is finite, otherwise it is infinite. Examples of finite binary strings include $00010100$, and $1111101010.$ Which of the following is $\text{TRUE}$ about the set of all finite binary strings and the set of all infinite binary strings?

  1. The set of all finite binary strings is countable while the set of all infinite binary strings is uncountable
  2. The set of all finite binary strings is uncountable while the set of all infinite binary strings is countable
  3. The set of all finite binary strings and the set of all infinite binary strings are both countable
  4. The set of all finite binary strings and the set of all infinite binary strings are both uncountable
  5. The set of all finite binary strings is countable while whether the set of all infinite binary strings is countable or not is not known
in Theory of Computation recategorized ago by

1 Answer

0 votes
0 votes

if length of each string is finite lets say N, we can enumerate it with sets of natural numbers, you can enumerate by beginning with N boxes, fill the first box with 2 possiblities, 0 or 1. second box with 2 more possibilities so 2x2. and so on. so they are countable and finite as well. in this case there are 2x2x2...2 = 2^N strings possible, at the last box, you will exhaust all the possiblities, and cover all possible strings. meas it is finite. this is only possible if length is finite.

but if length of each string is itself infinite, we cant count it. it follows from Cantor’s diagonal argument. If you arrange all the strings as per their digit, there is always one more infinite string that is different from all other strings, you can always form it so that it differs from string1 in 1st bit, from string2 in 2nd bit and so on. that is uncountable set.

Answer:

Related questions