7
$\begingroup$

In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all practical applications alphabets will be finite."

However, in Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Section 1.5.1 (p.28 / 2007), Hopcroft, Motwani and Ullman state that "[a]n alphabet is a finite, nonempty set of symbols." Further, Sipser "define[s] an alphabet to be any nonempty finite set." (Introduction to the Theory of Computation, 3rd Edition, Section 0.2 (p.13 / 2013).)

Is it correct that an alphabet may be infinite, even uncountably so? If so, are there any resources that discuss infinite alphabets?

Improve this question
$\endgroup$
1
  • $\begingroup$ Short answer, there is no standard definition of alphabet. It is true that modern usage usually assumes, even without stating it, that an alphabet is finite and non-empty. However, in some situations it does make sense to consider infinite alphabets. $\endgroup$
    – Yuval Filmus
    Feb 27 '17 at 0:56
9
$\begingroup$

It makes sense in some contexts in mathematics to consider strings or languages over infinite alphabets. For instance, this concept is used in the strong version of Higman's lemma. But a finite automaton requires a finite alphabet, and only finitely many symbols can actually appear in a single regular expression. So, specifically for the context of regular languages, alphabets must be finite.

It's not important whether you achieve this by declaring that "alphabet" means a finite set (as HMU and Sipser do) or whether you allow infinite alphabets and instead put the requirement of finiteness elsewhere than the definition of that word (as AU do).

Improve this answer
$\endgroup$
8
$\begingroup$

The usual convention in formal languages and automata theory is that an alphabet is finite.

However, there are certainly some cases where it's useful to think of an alphabet being infinite. For example, if one wants to define a universal Turing machine that can simulate the computations of any other Turing machine, then it's useful to have in mind some canonical infinite alphabet $\Sigma = \{ a_1, a_2 \ldots, \}$ and say that every Turing machine has an alphabet that is a finite subset of $\Sigma$.

In some pattern avoidance problems, it's useful to allow infinite alphabets. See, for example, my paper with Guay-Paquet.

People certainly have studied automata on infinite alphabets, and a google scholar search will turn up many papers. For example, I wrote a paper where the input alphabet of the automata is $\mathbb{Z}$.

Improve this answer
$\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.