Nondeterministic Finite Automata

by

⭐ Why do we need NFAs?

You might ask:
“Why use something that gives multiple choices? Isn’t that confusing?”

Actually, NFAs help us:

  • Design automata more easily
  • Think about languages in a more flexible way
  • Build DFAs later using simpler, intuitive ideas

And remember:
Even though NFAs look more powerful, they accept the exact same set of languages as DFAs — the regular languages. The advantage is simplicity, not extra power.

⭐ A simple example NFA

Let’s build a tiny NFA that accepts all strings that end with ‘a’.

In a DFA, you must create states carefully to keep track of previous symbols.
But with an NFA, we can design it in a very loose, natural way.

Here is the idea:

  • From the start, you can loop on both ‘a’ and ‘b’.
  • When you see an ‘a’, you may choose to jump to a final state.
  • That final state means: “Yes! The string ends with ‘a’.”

⭐ Diagram of a Simple NFA

        +-------+
        |  q0   |
        +-------+
        /   |    \
      a,b  a      ε
      /     \      \
     v       v      v
  +-------+        +-------+
  |  q0   |------->|  q1   |
  +-------+   a    +-------+
                    (final)

Explanation of the diagram:

  • q0 is the start state.
  • From q0, if you read ‘a’, you can:
  • Stay in q0, or
  • Jump to q1, the final state.
  • You can also loop on ‘b’ in q0.
  • The machine accepts a string if there is any path that reaches q1 after the last symbol.

This NFA is very relaxed — the machine can be in multiple states at once, which makes the design feel light and intuitive.

⭐ How NFAs process input

Let’s say the input string is: “bba”

When the last ‘a’ appears, the NFA has two options from q0:

  1. Stay in q0
  2. Move to q1 (final)

Since one option leads to a final state,
→ The string is accepted.

⭐ Key characteristics of NFAs (in simple words)

Here are the main points, explained casually:

✔ 1. Multiple transitions allowed

For the same symbol, an NFA can jump to many next states.

✔ 2. Epsilon transitions (ε moves)

Sometimes you can move to another state without reading any symbol —
like taking a small shortcut.

✔ 3. Accepting is easy

If any one path reaches a final state, the string is accepted.

✔ 4. Simple to design

For many patterns, the NFA diagram is much easier compared to building a DFA.

✔ 5. But not more powerful

Whatever an NFA can do, a DFA can also do.
It’s just that the DFA might need more states.

⭐ Real-life analogy

Think of an NFA as a group of friends exploring a forest.
Each friend can choose a different trail.
If even one friend finds the treasure, the whole group celebrates! 🎉

That’s exactly how acceptance works in an NFA.