Problem Solving in Automata, Languages, and Complexity

2 REGULAR LANGUAGES

The length of a string x, denoted by 1x1, is the number of symbols contained

in the string. For example, [strings1 = 7, ]CS5400( = 6, IlOOl( = 4. The

empty string, denoted by E, is a string having no symbol. Clearly, 1~1 = 0.

Example 1.1 How many strings
there which are of length n, where

over

n is

the alphabet A = {al, a2,...

a nonnegative integer?

? ak} are

Solution. There are n positions in such a string, and each position can hold
one of k: possible symbols. Therefore, there are Jc” strings of length exactly
n. cl

Let x and y be two strings, and write x = x122.. l x, and y = yly2 + 4 l ym ,
where each xi and each yj is a single symbol. Then, x and y are eqzsal if and
only if (1) n = m and (2) x:; = yi for all i = 1,... , n. For example, 0 1 # 0 10
and 1010 # 1110.
The basic operation on strings is concatenation. The concatenation x. y of
two strings x: and y is the string gy, that is, ~zf followed by y. For example,
CS54oO is the concatenation of CS and 5400. In particular, we denote x = x1,
xx = x2,..
l ,u
=x k, and define x0 = E. (Why is x0 = E? The reason
k
is that E is the identity for the operation of concatenation, and so x0 satisfies
the relation xOxk = x’+~ - - xk.) For example, 10101010 = (1O)4 = (1010)2,
(10)

(^0) = E It is obvious that xixj = xi+j for i,j > 0.
Let x be a string. A string s is a s&string of L if there exist strings y and
z such that x = ysx. In particular, when x = sz (y = E), s is called a prefix
of x; and when x = ys (z = E), s is called a SZ@%E of x. For example, CS is a
prefix of CS540o and 5400 is a suffix of CS5400.
For a string x over alphabet C, the reversal of x, denoted by xR, is defined
bY
xfL &
{

• ifx=E,
  xn l l l x2x1 ifx= ~lx2--x~, for Xxf,X2,***,Xn E Co

Example 1.2 For strings x and y, (xy)” = yRxR.

Proof. If x = E, then xR = E and hence (xY)~ = yR = yRxR. If y = 6, then

yR = E and hence (xY)~ = xR = yRxR. Now, suppose x = ~1x2 .**x~ and

Y- YlY2 ’ l ‘Yn7 with m, n > - 1. Then, (xT.J)~ = (~1x2 •*x~Y~Y~ •*Y,)~ =

Yn l ’ l y2y1xm ’ l l x2x1 = yRxR. Cl

Strings are also called words. Relations between strings form a theory,

called word theory. For instance, in word theory, we may be given an equation

of strings and are asked to find the solution strings for the variables in the

equation.