Non deterministic Finite Automata NFA

 

🤖 Formal Definition of NFA

An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages, like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions).

📘 An NFA is defined as a 5-tuple:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

Symbol	Description
$Q$	A finite set of states
$\Sigma$	A finite set called the input alphabet
$\delta$	The transition function:
$\delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q$ (a set of states)
$q_0$	The initial state, $q_0 \in Q$
$F$	The set of accepting states, $F \subseteq Q$

💡 Key Differences from DFA:

DFA	NFA
Only one transition per input	Multiple transitions possible
No ε-transitions	ε-transitions allowed
Deterministic	Nondeterministic – many possible paths
Easier to implement	Easier to design, but converted to DFA for implementation

🧪 Example NFA

Let’s construct an NFA that accepts all strings over $\Sigma = \{0,1\}$ that end with '01'.

In a given problem, the language accepts all strings ending with 01.

The language L= { 01,101,1101,001,11001,0101,11101,0001,1001,00101,…….}

✨ NFA Description:

• States: $Q = \{q_0, q_1, q_2\}$
  

• Alphabet: $\Sigma = \{0,1\}$
  

• Initial state: $q_0$

• Accepting state: $F=\{q_2\}$

🚀 Transitions:

• From $q_0$:

  • On 0, go to $q_0$ or $q_1$ (nondeterministic choice)

  • On 1, go to $q_0$

• From $q_1$:

  • On 1, go to $q_2$

• From $q_2$:

  • No transitions (final state)

🌟 How It Works:

This NFA allows multiple paths. It guesses the position where '0' is second last and checks for '1' immediately after.

If there is any computational path that accepts a string, then the machine accepts the string

Two ways to think about NFAs:

• Magic “Oracle”, which always picks the correct path to take
• Try all possible paths

✅ In Summary:

An NFA is a machine where for a given state and input, the next state is not uniquely determined.

It accepts a string if any one computation path ends in an accepting state.