0.1.4 Strings and Lan guages
The mathematical study of the “Theory of Computation” begins by
understanding the Mathematics of strings of symbols.
Alphabet: It is defined as a finite set of symbols.
Example: Roman alphabet {a, b, ...... z}.
“Binary Alphabet” {0, 1} is pertinent to the theory of computation.
String: A “string” over an alphabet is a finite sequence of symbols from that
alphabet, which is usually written next to one another and not separated by
commas.
(i) If Σ a = { , }
0 1 then 001001 is a string over Σ a .
(ii) If Σ b
a b
z
= { , , , )
K
then axyrpqstcd is a string over Σ b .
Length of String: The “length” of a string is its length as a sequence. The
length of a string w is written as |w|.
Example: |10011| = 5
Empty String: The string of zero length is called the “empty string”. This is
denoted by ∈.
The empty string plays the role of 0 in a number system.
Reverse String: If w w w
w n
= 1 2 K
where each w i ∈ Σ, the reverse of w is
w w
w
n n−1
1
L .
Substring: z is a substring of w if z appears consecutively within w.
As an example, ‘deck’ is a substring of ‘abcdeckabcjkl’.
Concatenation: Assume a string x of length m and string y of length n, the
concatenation of x and y is written xy, which is the string obtained by
appending y to the end of x, as in x x
x y y
y
m
n
1 2
1 2
K
K .
To concatenate a string with itself many times we use the “superscript”
notation:
x x
x x
k
k
K
6 7
4 8
4
=
Suffix: If w = xv for some x, then v is a suffix of w.
Prefix: If w = vy for some y, then v is a prefix of w.
Lexicographic ordering: The Lexicographic ordering of strings is the same as
the dictionary ordering, except that shorter strings precede longer strings.
18
Theory of Automata, Formal Languages and Computation