Wednesday, August 31, 2022

Finite Automata NFA DFA

 

Finite Automata

  • Finite automata are used to recognize patterns.
  • It takes the string of symbol as input and changes its state accordingly. When the desired symbol is found, then the transition occurs.
  • At the time of transition, the automata can either move to the next state or stay in the same state.
    • Finite automata have two states, Accept state or Reject state. When the input string is processed successfully, and the automata reached its final state, then it will accept.

    Formal Definition of FA

    A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F), where:

    1.      Q: finite set of states  

    2.      ∑: finite set of the input symbol  

    3.      q0: initial state   

    4.      F: final state  

    5.      δ: Transition function  

    Finite Automata Model:

    Finite automata can be represented by input tape and finite control.

    Input tape: It is a linear tape having some number of cells. Each input symbol is placed in each cell.

    Finite control: The finite control decides the next state on receiving particular input from input tape. The tape reader reads the cells one by one from left to right, and at a time only one input symbol is read.






Types of Automata:

There are two types of finite automata:

  1. DFA(deterministic finite automata)
  2. NFA(non-deterministic finite automata)



  • 1. DFA

    DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. In the DFA, the machine goes to one state only for a particular input character. DFA does not accept the null move.

    2. NFA

    NFA stands for non-deterministic finite automata. It is used to transmit any number of states for a particular input. It can accept the null move.

    Some important points about DFA and NFA:

    1. Every DFA is NFA, but NFA is not DFA.
    2. There can be multiple final states in both NFA and DFA.
    3. DFA is used in Lexical Analysis in Compiler.
    4. NFA is more of a theoretical concept.

    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.



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




    Transition Table:

    Present State

    Next state for Input 0

    Next State of Input 1

    →q0

    q0

    q1

    q1

    q2

    q1

    *q2

    q2

    q2

    NFA (Non-Deterministic finite automata)

    • NFA stands for non-deterministic finite automata. It is easy to construct an NFA than DFA for a given regular language.
    • The finite automata are called NFA when there exist many paths for specific input from the current state to the next state.
    • Every NFA is not DFA, but each NFA can be translated into DFA.
    • NFA is defined in the same way as DFA but with the following two exceptions, it contains multiple next states, and it contains ε transition.

    In the following image, we can see that from state q0 for input a, there are two next states q1 and q2, similarly, from q0 for input b, the next states are q0 and q1. Thus it is not fixed or determined that with a particular input where to go next. Hence this FA is called non-deterministic finite automata.

    Non-Deterministic finite automata

    Formal definition of NFA:

    NFA also has five states same as DFA, but with different transition function, as shown follows:

    δ: Q x ∑ →2Q
    

    where,

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

    Graphical Representation of an NFA

    An NFA can be represented by digraphs called state diagram. In which:

No comments:

Post a Comment