Theory of Automata

Introduction To Finite Automata

Finite Automata (FA) is a machine which accepts all the regular languages. It is used to recognize the patterns. It is also called finite state machine.

Working Of Finite Automata

  • The finite automata machine contains five tuple or elements.
  • It has some finite states and rules for moving from one state to another but it depends upon the given input symbol.

Basic diagram is given below

Working Of Finite Automata

A Finite Automata can be defined through its 5 tuples { Q, Σ, q, F, δ }. Where 

  • Q : Finite set of states.
  • Σ : set of Input Symbols.
  • q : Initial state.
  • F : set of Final States.
  • δ : Transition Function.

Types Of Finite Automata

FA is characterized into two types:

Types Of Finite Automata

 1) Deterministic Finite Automata (DFA) 

  • In a DFA, for a particular input symbol, the machine goes to one state only.
  • In DFA null (ε) move is not allowed. It means state cannot change without a input symbol. 

DFA contains 5 tuples {Q, Σ, q, F, δ}.

Q : set of all states.

Σ : set of input symbols.

q : Initial state.

F : set of final state.

δ : Transition Function, δ : Q X Σ –> Q.

2) Nondeterministic Finite Automata(NFA) 

  • NFA is similar to DFA except the Null (or ε) move. In NFA Null move is allowed. It means state can change without a input symbol. 
  • NFA also has similar 5 tuples {Q, Σ, q, F, δ} like DFA except transition function. It NFA Transition Function is given below

δ:  Q X (Σ U ε ) –> 2 ^ Q.

Some important points about DFA and NFA

  • Every DFA is NFA, but NFA is not DFA.
  • In NFA and DFA, there can be multiple final states.
  • DFA is used in Lexical Analysis in Compiler.
  • NFA mostly used as theoretical concept.
Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan


Pin It on Pinterest