2
$\begingroup$

I'm studying my notes for a formal language course and it them it states

The vast majority of languages over a finite alphabet cannot be represented by a finite specification.

I don't understand this. What is meant by "specification"? It then goes on to show why this is true by showing some sets of the alphabet are countably infinite and others are uncountably infinite.

$\endgroup$
  • $\begingroup$ Not entirely sure why there are uncountably many languages. Cantor diagonalization over the possible sentences? $\endgroup$ – MSalters Oct 15 '15 at 13:03
8
$\begingroup$

A specification in this sense is any description of the language that allows you to determine exactly what strings are in the language and what strings are not. We're usually quite vague about what exactly constitutes a specification since, ultimately, it doesn't matter. A specification must be describable by some finite string of characters, whether those characters represent English words ("The set of all strings consisting of some number of $a$s followed by the same number of $b$s"), mathematics ("$\{a^nb^n\mid n\geq 0\}$") or somethign else. As your notes go on to say, whatever reasonable meaning you give to "finite specification", there will only be countably many of them, whereas there are uncountably many languages.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.