<p>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 <a href="https://en.wikipedia.org/wiki/Higman%27s_lemma" rel="noreferrer">Higman's lemma</a>. 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.</p>

<p>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).</p>

CC BY-SA 3.0
2017-02-25T06:09:22.353Z
2017-02-25T06:09:22.353Z
David Eppstein
<p>The usual convention in formal languages and automata theory is that an alphabet is finite.  </p>

<p>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 <em>any</em> 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$.</p>

<p>In some pattern avoidance problems, it's useful to allow infinite alphabets.  See, for example, <a href="https://arxiv.org/abs/0901.1397" rel="noreferrer">my paper with Guay-Paquet</a>.</p>

<p>People certainly have studied automata on infinite alphabets, and a google scholar search will turn up many papers.  For example, I wrote a <a href="http://link.springer.com/chapter/10.1007/978-1-4614-6642-0_17" rel="noreferrer">paper</a> where the input alphabet of the automata is $\mathbb{Z}$. </p>

CC BY-SA 3.0
2017-02-25T12:13:24.700Z
2017-02-25T12:13:24.700Z
Jeffrey Shallit
<p>As already mentioned the classical theory of regular languages crucially depends on the finiteness of the alphabet. But there have been a lot of recent works on extending this to alphabets that are <a href="https://www.mimuw.edu.pl/%7Ebojan/upload/main-10.pdf" rel="nofollow noreferrer">&quot;slightly infinite&quot;</a>, typically of the form Σ×A where Σ is a finite set of labels and A is a countably infinite set of &quot;atoms&quot;. Morally, the atoms can only be inspected by comparing two of them for equality; this is made formal in the theory of <em>nominal sets</em> by invariance properties with respect to the action of permutations of A. See for instance the introduction of this paper by Bojańczyk and Stefański: <a href="https://doi.org/10.4230/LIPIcs.ICALP.2020.113" rel="nofollow noreferrer">https://doi.org/10.4230/LIPIcs.ICALP.2020.113</a></p>

CC BY-SA 4.0
2024-12-11T21:24:54.447Z
2024-12-11T21:24:54.447Z
Lê Thành Dũng 'Tito' Nguyễn
<p>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."</p>

<p>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 <em>alphabet</em> is a finite, nonempty set of symbols." Further, Sipser "define[s] an <strong><em>alphabet</em></strong> to be any nonempty finite set." (Introduction to the Theory of Computation, 3rd Edition, Section 0.2 (p.13 / 2013).)</p>

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

CC BY-SA 3.0
2017-02-27T00:56:05.523Z
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.
Yuval Filmus
<fl.formal-languages><computability><automata-theory><regular-language><set-theory>
In the context of regular languages, must the alphabet be finite?
sam
# In the context of regular languages, must the alphabet be finite?

(Asked by: username_0 on 2017-02-25)

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?

**Tags:** fl.formal-languages, computability, automata-theory, regular-language, set-theory

> **Comments:**
> **username_1**: 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.  

---

## 3 answers

### Answer by username_2 on 2017-02-25. Score: 11

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](https://en.wikipedia.org/wiki/Higman%27s_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).


---

### Answer by username_3 on 2017-02-25. Score: 9

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](https://arxiv.org/abs/0901.1397).

People certainly have studied automata on infinite alphabets, and a google scholar search will turn up many papers. For example, I wrote a [paper](http://link.springer.com/chapter/10.1007/978-1-4614-6642-0_17) where the input alphabet of the automata is $\mathbb{Z}$.


---

### Answer by username_4 on 2024-12-11. Score: 3

As already mentioned the classical theory of regular languages crucially depends on the finiteness of the alphabet. But there have been a lot of recent works on extending this to alphabets that are ["slightly infinite"](https://www.mimuw.edu.pl/%7Ebojan/upload/main-10.pdf), typically of the form Σ×A where Σ is a finite set of labels and A is a countably infinite set of "atoms". Morally, the atoms can only be inspected by comparing two of them for equality; this is made formal in the theory of *nominal sets* by invariance properties with respect to the action of permutations of A. See for instance the introduction of this paper by Bojańczyk and Stefański: <https://doi.org/10.4230/LIPIcs.ICALP.2020.113>


---

