I\'m going over some of the pre-requisite math regarding Automata theory, and fi

Question

I'm going over some of the pre-requisite math regarding Automata theory, and finite representations.

I read the following:

If ? is a finite alphabet the set of all strings over the alphabet (?*) is countably infinite.

The set of all possible languages over an alphabet ? is uncountably infinite.

How can the set of languages possible from ? be uncountably infinite, yet the possible application of that alphabet to a language be countably infinite?

Can I ask those replying to not use too much complex notation, as I'm not a mathematics wizz.

Explanation / Answer

Here is a simpler situation highlighting the difference. The set of finite binary strings is countable. The set of infinite binary strings is uncountable.

Another example: the set of numbers with finite decimal expansion is countable. The set of numbers with infinite decimal expansion is uncountable.

The reason that the number of languages is uncountable is that you have infinitely many choices: for each word, you can decide whether it's in the language or not. That's why it's like that infinite binary string considered above.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.