Finite Automata In TOC

Finite Automata (FA)  is a machine in TOC that accepts all the regular languages. These abstract machines operate within a finite set of states and transition between these states based on inputs from a finite alphabet. Finite automata have some finite states and rules for moving from one state to another, but it depends upon the given input symbol.

Formal definition of a Finite Automaton

A Finite Automata contains five tuples { Q, Σ, q, F, δ }. Where 

  • Q is a set of finite states.
  • ∑ represents a finite set of symbols or alphabets.
  • δ represents the transition function.
  • q0 is the initial state (q0 ∈ Q).
  • F is a set of final states of Q (F ⊆ Q).

States, Alphabet, Transition Function, Initial State, and Final States are the Key components of finite automata.

Working Of Finite Automata

Every automata takes a language as input, processes it through some automata machines, and gives an output in the form of a set of states. The following descriptive diagram

Working Of Finite Automata

Types Of Finite Automata in TOC

Following are two types of finite automata. 

Types Of Finite Automata

1. Deterministic Finite Automata (DFA) 

In a DFA,

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

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

  • Q: Set of all states.
  • Σ: Set of input symbols.
  • δ: Transition Function, δ: Q X Σ →Q
  • q: Initial state.
  • F: Set of final state.

2. Nondeterministic Finite Automata (NFA) 

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

δ:  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 is mainly used as a theoretical concept.