Introduction To Finite Automata

Finite Automata (FA) is a machine 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

Types Of Finite Automata

Following are two 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.