Basic Concepts of Automata | Finite Automata Concepts

Explain symbols used in finite automata with their units

a)     Symbol:

•          Symbol 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:

•          Alphabet 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:

•          String 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:

•          Length of string 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:

•          Empty string 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  

Matched Content Ads: