Lecture No. 15

Dated: 30-10-2024

Non Deterministic Finite Automaton

A non deterministic finite automaton is a transition graph¹ with a unique initial state and single letter as label for transitions.
It is a collection of following things:

• Finite many states with one initial and some final states.
• Finite set² of input letters \(\Sigma = \{a, b, c\}\).
• Finite set² of transitions. \(\Lambda\) is not a valid transition and there may be more than one transitions for a letter or no transitions at all.

It can be considered as an intermediate structure between finite automaton³ and transition graph¹

Note

To remove a loop at a state, it is to be noted that the finite automaton³ may be converted to a non deterministic finite automaton, as a circuit.

The following finite automaton³

can be converted into following non deterministic finite automaton.

Converting a Finite Automaton³ into Equivalent Non Deterministic Finite Automaton

According to Kleene's Theorem,⁴ if a language is accepted by a finite automaton³ then there exists a transition graph¹ which accepts that language as well.
Since the non deterministic finite automaton is also a transition graph¹ so the language accepted by the finite automaton³ is also accepted by the non deterministic finite automaton, which makes them equivalent.

\[r = (a + b)^*b\]

Finite Automaton³

Non Deterministic Finite Automaton

References

---

1. Read more about transition graph. ↩↩↩↩

2. Read more about sets. ↩↩

3. Read more about finite automaton. ↩↩↩↩↩↩↩

4. Read more about Kleene's theorem. ↩