EF Alphabets and words

Skip to main content

Section 9.6 Alphabets and words

alphabet: 🔗
any set can be considered an alphabet
letters: 🔗
the elements of an alphabet set
word: 🔗
a finite-length, ordered list of letters
$Σ^{*}$: 🔗
the set of words using alphabet set $Σ$

Remark 9.6.1.

Even if the alphabet set

Σ

is the usual English-language alphabet, we do not restrict ourselves to actual English-language words — nonsense words are allowed.

Example 9.6.2. English is not a full set of words.

Using

Σ = {a, b, c, \dots, y, z},

words

math, qwerty, aabbccddijzuuu

are examples of elements in

Σ^{*} .

So, ignoring punctuation, hyphenation, and capitalization, the English language is a proper subset of

Σ^{*} .

Example 9.6.3. If digits are letters then numbers are words.

Using alphabet

Σ = {0, 1, 2, \dots, 9},

then

N ⫋ Σ^{*} .

Checkpoint 9.6.4.

Why is

N \neq Σ^{*}

in Example 9.6.3?

In computing science, a certain set of words is of particular importance.

binary word: 🔗
a word using alphabet ${0, 1}$
binary string: 🔗
synonym for binary word

Warning 9.6.5.

Order matters! For example, using the alphabet

Σ = {a, b, c, \dots, y, z},

the words

ab

and

ba

are different words in

Σ^{*} .

length (of a word): 🔗
given $w \in Σ^{*},$ the length of $w$ is the number of elements from $Σ$ used to form $w,$ counting repetition
$| w |$: 🔗
length of the word $w \in Σ^{*}$

Example 9.6.6.

Using alphabet

Σ = {a, b, c, \dots, y, z},

we have

\begin{aligned} | qwerty | & = 6, & | aabab | & = 5 . \end{aligned}

The concept of length allows us to identify some special subsets and a special element of

Σ^{*} .

$Σ_{n}^{*}$: 🔗
for $n \in N,$ the subset of $Σ^{*}$ consisting of all words of length $n$
empty word: 🔗
given an alphabet $Σ,$ we always consider $Σ^{*}$ to contain a unique word of length $0$
$\emptyset$: 🔗
the empty word

<Prev ^Top Next>