Finite Automata, DFA and NDFA theory

Here I will discuss Finite Automata according to examination point of view, not in details. this will contain only definition and Numericals with solution that are important for final examination.

Finite Automata

Described by 5 tuples ( Q , Σ , δ , q₀ , F ), where

• Q is a finite set of states(denoted by capital letters like A, B... etc).
• Σ is a finite set of input terminals (Denoted by small letters like a, b... etc).
• δ is the transition function, that is, δ: Q × Σ → Q.
• q₀ is the initial state.
• F is a set of final state

Since input tape contains only finite number of blocks , so it is call Finite. here reading head read only one block at a time and move only in one direction and controlled by finite control.

Deterministic Finite Automata (DFA):

Same tuples like Finite Automata  ( Q , Σ , δ , q₀ , F ) 
, but only difference in transition function δ .
 δ means : for every input, there will be a unique state,

  i.e,        Q(state)× Σ(input) → Q(state)

For exam. suppose for any state q, if we apply input 0, then we will get only one state that is q'.

In above diagram, there are three transition (A to C , A to B, A to D) for input "a" from state "A" . so this is not DFA ,because for single input, we are getting 3 states.

Non-Deterministic Finite Automata (NDFA):

In NDFA, All tuples are same like Finite Automata except transition function that is mentioned below:

Transition function     δ :  Q × Σ → P(Q) ,    where P(Q) is the power set of Q.


NDFA is same like DFA. only difference is that:  In DFA, we get only one state for a single input. but in NDFA, we get more than one state for single input.

Above transition diagram is an example of NDFA. Because in state "A", when we apply input "a" then we get three states (C,B and D).