# Differentiate between NFA and DFA

## Deterministic finite Automata

The word “deterministic” refers to the fact that the transition is deterministic. There is only one state to which an automaton can transit from the current state each input. The word “finite” implies that number of state are finite. A finite automata consists of five parts:

1. 1. A finite set of states, represented as Q.
2. 2. A finite set of alphabet, represented as Σ.
3. 3. An initial state, represented as q0 .
4. A set of accepting states. An accepting state or final state is for ‘Yes’ answer. It is a subset of Q and is represented as F.
5. F ⊆ Q
6. 5. A next state function or a transition function. Next state depends on the current state and the current input. It is a function from Q X Σ to Q. It is repesented as δ .

Finite automata,

M = (Q, Σ, δ, q0, F), where

Q is a set of states.
Σ is a set of alphabet.
q0 ϵ Q is the initial state
F ⊆ Q is the set final states, and δ, the transition function, is a function from Q X Σ to Q.

## Non-Deterministic finite Automata

Non-Determinstic finite automata can reside in multiple states at the same time. The concept of non -deterministic finite automata is being explained with the help of the transition diagram.

IF the automata is in the state q0 and the next input symbol is 1, then the next state will be either :

1) q0 2) q1

Thus, the move from q0 and the next input symbol is 1, cannot be determined uniquely. Such machines are called Non- deterministic automata.

– A Non- deterministic finite automata can be in several states at any time. Thus, NFA can guess about an input sequence.

– Every NFA can be converted into an equivalent DFA.

– An NFA can be designed with fewer states compare to its deterministic counterpart.

– Due to non-determinism, NFA take more time to recognize a string.

## Definition of NFA

A Non – deterministic finite Automata is a 5 tuple.

M = {Q, Σ, δ, q0, F}

Q = A finite set states

Σ = A finite set of input

δ = A transition function from Q X Σ to the power set of Q i.e.to 2Q

q0 = q0 ϵ Q is the start / initial state

F = F  Q is a set of final / accepting states.

The NFA, for table can be formally represented as,

({q0, q1, q2}, {0, 1},δ ,{q2})