7.1 BASIC CONCEPTS OF AUTOMATA THEORY
Before begin to the study of automata theory we shall first introduce the basic concepts and
definitions used thereon. These concepts include the understanding of the terms ‘alphabet’,
‘string’, ‘language’, etc.7.1.1 Al phabets
An alphabet is an atomic, finite and nonempty set of symbols. We use the convention Σ for an
alphabet. For example,
l Σ = {a, b, ........, z}, set of all lower case letters.
l Σ = {0, 1}, set of binary symbols.
l Σ = {0, 1, 2, ......, 9}, set of numeric symbols.
l Σ = { 0, 1, 2, ......9, a, b, ....., z}, set of alphanumeric symbols.7.1. 2Strings
A string is the finite ordering of symbols chosen from some alphabet Σ. For example, abc, acb,
bca, abca, are some of the strings from the alphabet Σ = {a, b, c}. Note that a, b, and c are also
the strings from the alphabet {a, b, c}. When we write a, b, and c as the elements of Σ then these
refers as symbols not strings. The strings can be usually classified by their length, that is, the
number of occurrences of the symbols in the string. The standard denotation for the length of
the string x is |x|. For example, | abc | = 3 and | a | = 1.
A string of zero occurrences of symbols is called empty string or null string. We denote it
by ∈ (read as “epsilon”) such that | ∈ | = 0. Thus, ∈ is a string chosen from any alphabet Σ
whatsoever.
7.1.3 P ower of Σ
For any alphabet Σ, the power of Σ i.e., Σk where k is any positive integer expresses the set of all
strings of length k formed over Σ. For example, let Σ = {0, 1} then
l Σ^0 = {∈}
l Σ^1 = {0, 1}
l Σ^2 = {00, 01, 10, 11}
l ............................
l Σk = {00......0, 0........1, 1.......0, 1........1, ........}, each string is of length k.7
168Introduction to Languages
and Finite Automata