# In the context of regular languages, must the alphabet be finite?

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?

• 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. Feb 27 '17 at 0:56

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$.
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}$.