694
Modeling Arithmetic, Computation, and Languages
Recall that the notation (1, 2), for example, means that 1 maps to 2, 2 maps to 1,
and unnamed elements map to themselves. The composition (1, 2) + (1, 3) is done
from right to left, so
By (1, 3)
By (1, 2)
1 S 3 S 3
2 S 2 S 1
3 S 1 S 2
resulting in (1, 3, 2). Thus a 2 + a 3 = (1, 2) + (1, 3) = (1, 3, 2) = a 6 .
■
PrACtiCe 13
a. Complete the group table for 3S 3 , + 4.
+
a 1
a 2 a 3 a 4 a 5 a 6
a 1
a 2
a 6
a 3
a 4
a 5
a 6
b. Is 3S 3 , + 4 a commutative group?
3S 3 , + 4 is our first example of a noncommutative group (although 3M 2 (Z), # 4 was a
noncommutative monoid).
The next example is very simple but particularly appropriate because it appears in several areas of computer science, including formal language theory and
automata theory.
example 11
Let A be a finite set; its elements are called symbols and A itself is called an
alphabet. A* denotes the set of all finite-length strings, or words, over A. A* can be
defined recursively (as in Example 6 in Chapter 3), where # denotes concatenation
of strings:
a. The empty string l (the string with no symbols) belongs to A*.
b. Any single member of A belongs to A*.
c. If x and y are strings in A*, so is x # y.
Thus, if A = 5a, b6, then abbaa, bbbbba, and a are all strings over A, and abbaa # a
gives the string abbaaa. From the recursive definition, any string over A contains
only a finite number of symbols. The number of symbols in a string is called its
length. The empty string l is the only zero-length string.