Definition 2.4. Given an alphabet Σ, given any two strings u, v ∈ Σ∗ we define the following notions as follows:

• prefix
• suffix
• substring

We say that u is a proper prefix (suffix, substring) of v iff u is a prefix (suffix, substring) of v and u ̸= v.

Definition 2.5: lexicographic ordering: <_

Definition 2.6. Given an alphabet Σ, a language over Σ (or simply a language) is any subset L of Σ∗. If Σ ̸= ∅, there are uncountably many languages.

Finite, Infinite, Countable, and Uncountable Sets