Finite Automata - NFA and DFA

 

Finite Automata - is the simplest machine to recognize patterns.

A finite Automata consists of :

   Q : Finite set of states.

Σ : Set of Input Symbols.

q : Initial State

F : Set of Final States

δ : Transition Function

Formal specification of machine is {Q, Σ, q, F, δ}

FA is characterized into two types:

Deterministic Finite Automata(DFA)

Non Deterministic Finite Automata(NFA)

Deterministic Finite Automata

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

Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

In DFA, when an input character is given the machine goes to one state only.
A transition function is defined on every state for every input symbol.

ALso in DFA null (or ε) move is not allowed.

 i.e., DFA cannot change state without any input character.

For example, below DFA with Σ = {0, 1} accepts all strings ending with 0

2) Nondeterministic Finite Automata(NFA)

NFA is similar to DFA except following additional features:
1. Null (or ε) move is allowed i.e., it can move forward without reading symbols.
2. Ability to transmit to any number of states for a particular input.

Due to above additional features, NFA has a different transition function, rest is same as DFA.
δ: Transition Function
δ:  Q X (Σ U ε ) --> 2 ^ Q. 
As you can see in transition function is for any input including null (or ε), NFA can go to any state number of states.

Some Important Points:
1. Every DFA is NFA but not vice versa.
Justification:
Since all the tuples in DFA and NFA are the same except for one of the tuples, which is Transition Function (δ)
In case of DFA
δ : Q X Σ --> Q
In case of NFA
δ : Q X Σ --> 2Q
Now if you observe you’ll find out Q X Σ –> Q is part of Q X Σ –> 2Q.

In the RHS side, Q is the subset of 2Q which indicates Q is contained in 2Q or Q is a part of 2Q, however, the reverse isn’t true. So mathematically, we can conclude that every DFA is NFA but not vice-versa. Yet there is a way to convert an NFA to DFA, so there exists an equivalent DFA for every NFA.
2. Both NFA and DFA have same power and each NFA can be translated into a DFA.
3. There can be multiple final states in both DFA and NFA.
4. NFA is more of a theoretical concept.
5. DFA is used in Lexical Analysis in Compiler.