What is DFA ? | How DFA is constructed

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
	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
	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