Posted in Blog

DFA (Deterministic finite automata)

DFA (Deterministic finite automata)

  • DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. The finite automata are called deterministic finite automata if the machine is read an input string one symbol at a time.
  • In DFA, there is only one path for specific input from the current state to the next state.
  • DFA does not accept the null move, i.e., the DFA cannot change state without any input character.
  • DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.

In the following diagram, we can see that from state q0 for input a, there is only one path which is going to q1. Similarly, from q0, there is only one path for input b going to q2.

Deterministic finite automata

Formal Definition of DFA

A DFA is a collection of 5-tuples same as we described in the definition of FA.

 
  1. Q: finite set of states  
  2. ∑: finite set of the input symbol  
  3. q0: initial state   
  4. F: final state  
  5. δ: Transition function  

Transition function can be defined as:

 
  1. δ: Q x ∑→Q  

Graphical Representation of DFA

A DFA can be represented by digraphs called state diagram. In which:

  1. The state is represented by vertices.
  2. The arc labeled with an input character show the transitions.
  3. The initial state is marked with an arrow.
  4. The final state is denoted by a double circle.

Example 1:

 
  1. Q = {q0, q1, q2}  
  2. ∑ = {0, 1}  
  3. q0 = {q0}  
  4. F = {q2}  

Solution:

Transition Diagram:

Deterministic finite automata

Transition Table:

Present StateNext state for Input 0Next State of Input 1
→q0q0q1
q1q2q1
*q2q2q2

Example 2:

DFA with ∑ = {0, 1} accepts all starting with 0.

Solution:

Deterministic finite automata

Explanation:

  • In the above diagram, we can see that on given 0 as input to DFA in state q0 the DFA changes state to q1 and always go to final state q1 on starting input 0. It can accept 00, 01, 000, 001….etc. It can’t accept any string which starts with 1, because it will never go to final state on a string starting with 1.

Example 3:

DFA with ∑ = {0, 1} accepts all ending with 0.

Solution:

Deterministic finite automata

Explanation:

In the above diagram, we can see that on given 0 as input to DFA in state q0, the DFA changes state to q1. It can accept any string which ends with 0 like 00, 10, 110, 100….etc. It can’t accept any string which ends with 1, because it will never go to the final state q1 on 1 input, so the string ending with 1, will not be accepted or will be rejected.

Post Views: 487
Share: