Design and Analysis of Algorithms

626 Design and Analysis of Algorithms

5. Fast transformational computation such as FFT

6. Secure communication, Internet

7. Effi cient approximations

8. Analysis of electrical networks

9. Puzzles

A.6 FORMAL LANGUAGES

A.6.1 Strings

Let Σ be a fi nite, non-empty set of symbols, called an alphabet. A string (or word) over Σ is a fi nite sequence

of symbols written side-by-side. For example, abacc is a string over {a, b, c}.

The length of string s over Σ, denoted by |s|, is the total number of occurrences of symbols in s.

For example, |abacc| = 5.

A string of length 0 is called an empty string or null string, denoted by ∈ or λ.

A.6.2 Binary Operation on Strings

Let x = a

1

a

2

… a

m

and y = b

1

b

2

… b

n

be strings over Σ, of lengths m and n respectively ...