Language of Finite Strings is Countable

[Eric Postpischil]

Mitch Marks writes:

> Give me a putative mapping from the natural numbers to the sentences of
> this language, and I construct a sentence which differs from your sentence #1
> in place #1, differs from your #2 in place #2, etc, yet which accords with the
> grammar. This is easy to do: if your sentence #n has length n or greater, I
> pick the other character at position #n; if your sentence #n is shorter than n
> characters, I freely pick a or b. My sentence is a nonempty string of a and
> b, so it's in the language.

The sentence constructed is not in the language because it is not of finite
length.


-- edp
Eric Postpischil
"Always mount a scratch monkey."