Basic Concepts of Automata

a)     Symbol:

•          It is a basic entity or basic building block of automata. 
•      It could be letters, digits or any symbols.
•      E.g. a,b,……,z, A,B,…..,Z,0,1,…..,9,@,$,# etc

b)  Alphabet:

•          It is any finite set of symbols.It is denoted by ∑.
•      There are two types of alphabets

•          Numerical Alphabet: It contains digits as symbols. E.g. ∑={0,1}
•          Character Alphabet: It contains characters or letters as symbols. E.g. ∑={a,b}

c)   String:

•          It is a finite sequence of symbols taken from alphabet ∑
•          It is denoted by  w or s
•          Example1: w=abba is valid string over ∑={a,b}
•          Example2: w=010101 is valid string over ∑={0,1}

d)  Length of string:

•          It is the total numbers of symbols present in the string
•          It is denoted by |w| or |s|
•          Example1:If w= abba then |w|=4
•          Example1:If w= 010101 then |w|=6

e)  Empty String:

•          It is the string with zero occurrences of symbols i.e. |w|=0
•          It is also called as null string denoted by Ɛ or  λ

f)    Power of ∑: (For Example over ∑={0,1})

•          ∑⁰=Set of all strings of length 0    i.e. ∑={ Ɛ}
•          ∑¹= Set of all strings of length 1   i.e. ∑={0,1}
•          ∑²= Set of all strings of length 2  i.e. ∑={00,01,10,11}
•          ∑³= Set of all strings of length 3  i.e. ∑={000,001,010,011,100,101,110,111}
•          ∑ⁿ= Set of all strings of length n  

g)   Kleene closure:

•          It is the infinite set of all possible strings of all possible lengths including Ɛ
•          It is denoted by ∑*
•          So ∑*=∑⁰ U ∑¹ U ∑² U ∑³U…..
•       For example over ∑= {0,1}

        ∑* ={ Ɛ,0,1,00,01,10,11, 000,001,010,011,100,101,110,111,……}

h)  Positive Closure:

•          It is the infinite set of all possible strings of all possible lengths excluding Ɛ
•          It is denoted by ∑+
•          So ∑+=∑* - { Ɛ  }
•          So ∑+= ∑¹ U ∑² U ∑³U…..
•          For example over ∑= {0,1}

            ∑* ={ 0,1,00,01,10,11, 000,001,010,011,100,101,110,111,……}

i) Language:

•          It is set of all string taken from ∑*
•          So it is the subset of ∑*
•          It is denoted by L
•          There are two types of languages

                      Finite Language: It is a finite set of string.

• E.g.1: If L1={ Set of strings of length 2 } then { 00,01,10,11 } over the alphabet ∑={0,1}
• E.g.2: If L2={ Set of strings of length 3} then{ 000,001,010,011,100,101,110,111} over the alphabet ∑={0,1}

     Infinite Language: It is infinite set of string.

• E.g.1: If L3={ Set of strings of length which starts with 0 } then { 0,00,01,000,001, 010, 011,0000,………} over the alphabet ∑={0,1}