Theory of Computation | NFA - Non-deterministic Finite Automata

Prerequisites :

• Symbols, Alphabets, Strings and Language
• Types of Automata and Representation.
• DFA - Deterministic Finite Automata

When there is a chance for multiple state changes on a given single input, the non-deterministic in autoama handles the scenario.

The non determinism may even lead a in to null states.

Non-deterministic Finite Automata(NFA) are pseudo machines, means cannot be implemented in reality, even though they are finite state machines.

But of course NFA are very useful to resolve problem by exhaustive searching and backtracking.

---

A null state is represented using Greek letter Φ

The figure represents a NFA, which accepts all strings which starts with alphabet 'a'

Here we have two states, A and B.

so, set of all states Q = {A, B}

and set of all symbols Σ = {a, b}

Final state F = {B} and initial state q₀ = { A }

When input 'a' is given to state A, the state changes to B

But input 'b' on A leads to a null(Φ) state.

Any input on state B loop backs to state B itself.

since a alphabet/symbol input can give more than one final state, we have to track all the possible way a string can end up with.

And if there is a path, which ends on any final state the string considers as acceptable.

Example:

string 'baa', on giving its first symbol 'b' as input to initial state A leads to Φ state, and no further transitions possible.

This scenario is known as dead configuration, where there is no further movements possible, and the string gets rejected.

for string 'ab', the first alphabet 'a' gives transition to state B and second alphabet 'b' loop backs to same final state.

This the final state of string 'ab' is at final state B, it considers as a acceptable string.

String 'baa' follows a path A ➡ Φ and 'ab' follows A ➡ B .

Since in NFA a alphabet/symbol input can give more than one transition, there might be multiple path for a given string.

In all of those possible paths, if any one of them ends in final state, the string will be acceptable.

The path followed by strings in NFA varies from string to string. So these path cam be either a subset of Q(set of all states) or a Q itself or even be a null set.

so, state transition function delta can be represented as δ : Q x Σ ➡ {all subsets of Q}

Since Q is also a part of all possible subsets(2^Q in number), every DFA is a subset of NFA

| Deterministic Finite Automata | epsilon - NFA | Home |