9.6: Alphabets and words
- Page ID
- 90681
any set can be considered an alphabet
the elements of an alphabet set
a finite-length, ordered list of letters
the set of words using alphabet set \(\Sigma\)
Even if the alphabet set \(\Sigma\) is the usual English-language alphabet, we do not restrict ourselves to actual English-language words — nonsense words are allowed.
Using \(\Sigma = \Sigma = \{a, b, \ldots, y, z\} \text{,}\) words
\begin{equation*} \mathrm{math}, \; \mathrm{qwerty}, \; \mathrm{aabbccddijzuuu} \end{equation*}
are examples of elements in \(\Sigma^{\ast}\text{.}\) So, ignoring punctuation, hyphenation, and capitalization, the English language is a proper subset of \(\Sigma^{\ast}\text{.}\)
Using alphabet \(\Sigma = \{ 0,\, 1,\, 2,\, \dotsc,\, 9 \}\text{,}\) then \(\mathbb{N} \subsetneqq \Sigma^{\ast}\text{.}\)
Why is \(\mathbb{N} \neq \Sigma^{\ast}\) in Example \(\PageIndex{2}\)?
In computing science, a certain set of words is of particular importance.
a word using alphabet \(\{0,1\}\)
synonym for binary word
Order matters! For example, using the alphabet
\begin{equation*} \Sigma = \{a, b, \ldots, y, z\} \text{,} \end{equation*}
the words \(\mathrm{ab}\) and \(\mathrm{ba}\) are different words in \(\Sigma^{\ast}\text{.}\)
given \(w \in \Sigma^{\ast}\text{,}\) the length of \(w\) is the number of elements from \(\Sigma\) used to form \(w\text{,}\) counting repetition
length of the word \(w \in \Sigma^{\ast}\)
Using alphabet \(\Sigma = \Sigma = \{a, b, \ldots, y, z\}\text{,}\) we have
\begin{align*} \vert \mathrm{qwerty} \vert & = 6 \text{,} & \vert \mathrm{aabab} \vert & = 5 \text{.} \end{align*}
The concept of length allows us to identify some special subsets and a special element of \(\Sigma^{\ast}\text{.}\)
for \(n \in \mathbb{N}\text{,}\) the subset of \(\Sigma\) consisting of all words of length \(n\)
given an alphabet \(\Sigma\text{,}\) we always consider \(\Sigma^{\ast}\) to contain a unique word of length \(0\)
the empty word