IOT-Courses: July 2020

Automata Concepts

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

DFA:

Ø The finite automata is called deterministic finite automata, is there is only one path for specific input from current state to next state.

Ø In DFA, for each input symbol, one can determine the state which machine will move.

Ø As it has finite number of states, the machine is called deterministic finite machine or deterministic finite automata

Graphical Representation:

Ø A DFA is represented by digraphs called state diagram or transition diagram

Ø the vertices represent the states

Ø the arcs/ edges labelled with an input symbols shows the transitions

Ø Initial state is denoted by single circle and arrow pointing towards it(i.e. incoming arrow)

Ø The final state is denoted by two concentric circles

Formal definition of DFA:

Ø A DFA can be represented by 5-tuple or Quintuple machine

M= (Q, ∑, δ, q₀, F), where −

· Q is a finite set of states.

· ∑ is a finite set of symbols, called the input alphabet of the automaton.

· δ is the transition function/mapping function which maps

Q x ∑ à Q (Here x is cartesian Product)

Above mapping is usually represented by

1. Transition function/Mapping function

2. Transition diagram / Transition graph / Transition State diagram/ State diagram

3. Transition table/Transition state table/Mapping table

· q₀ is the initial state from where any input is processed (q₀ ∈ Q).

· F is a set of final state/states of Q (F ⊆ Q).

POINTS TO REMEMBER:

To design FA ,we need to consider following points

1) No. of states= Length of string +1 ==> Applicable only for DFA

2)A string is said to be accepted by FA,if and only if,after applying that string if we are able to reach from initial state to final state.Otherwise it is rejected.

3)If language is finite language then state diagram of DFA will contain Dead state/Trap state

4)If language is infinite language then state diagram of DFA will contain dead state and loops as well.

Ø Example1 : Let a DFA can be Q={A,B,C}, ∑={0,1}, q₀={A},F={C} and δ is given by the table

Present State	Next State
Present State	Input 0	Input 1
àA	A	B
B	C	A
*C	B	C

SOLUTION:

Given Q={A,B,C}, ∑={0,1}, q₀={A},F={C} and δ is given by the table

Present State	Next State
Present State	Input 0	Input 1
àA	A	B
B	C	A
*C	B	C

1)Transition function:

By using the below formula we can easily write the transition functions

δ(Present State, Input Symbol)=Next State

δ( A, 0)= A ,δ (A,1)= B

δ( B, 0)= C ,δ (B,1)= A

δ( C, 0)= B ,δ (C,1)= C

2)Transition diagram:

DFA SOLVED EXAMPLES

IOT-Courses

Pages

Basic Concepts of Automata