Discrete Mathematics for Computer Science

Languages and Regular Sets

A particularly important application of finite sequences is languages. The words of a lan-

guage are finite sequences of symbols or strings from some finite set of symbols, called

an alphabet. For example, begin or wherefore or a or string or doesn't or cooperation are

words. In this context, a sequence is written in the form begin, not the form b e g i n.

The symbols in the words themselves will be underlined in this section to distinguish be-

tween talking about a word (underlined) and using a word (not underlined). The operation

of concatenation defined for two words x and y, denoted as x • y, lists the second word

immediately after the first word. Concatenation is shown by just running the sequences

together-for example, book • keeper = bookkeeper. The examples, so far, all use the

characters of the English alphabet, including apostrophes. One could just as well look at
any other alphabet, such as the Spanish alphabet, which is slightly different, or all the keys
on a computer keyboard that print characters on the screen except for space. In general, we
can define words relative to any alphabet. More generally, for any two sets of words A and
B, we let

A- B = {x -y :x E A and y E B}

Definition 1. An alphabet is a finite set.

Definition 2. Let E be an alphabet. Then, E is the set of all finite sequences of elements
of E. The elements of V are strings or words over E. The empty string, the string with
no symbols, is denoted A or r.

Example 1.

(a) Let E = {a} (a set with one element). Then, the set of words over E is {A, a, aa, aaa,
aaaa, aaaaa, aaaaaa, ... }.
(b) Let E = {a, b}. Then, the set of words over E is {A, a, b, aa, ab, ba, bb, aaa, aab, aba,
abb, baa, bab, bba, bbb, ... 1

Definition 3. A language over an alphabet E is a set of strings over E. Alternatively, a
language is a subset of V*.

One way to study language is to define a language to be the set of words in the latest
edition of the language's standard dictionary. So, by this definition, cooperation E English
and psymathastrygronomy 0 English. Similarly, to study a computer language, you define

587