Lecture No. 16

Dated: 30-10-2024

Application of Non Deterministic Finite Automaton¹

There is an important application of non deterministic finite automaton¹ in artificial intelligence.

Imagine a maze as such where - is the initial state and + is the final state.

-	1	2	3
4	L	5	O
6	M	7	P
8	N	9	+

One is allowed to only move on the numeric tiles.
We can determine the number of ways someone can move from - to + using the following non deterministic finite automaton¹

It is shown that the shortest string² which is accepted by the machine is \(aaaaaa\).

Note

1. Every finite automaton³ can be considered to be a non deterministic finite automaton¹ as well but the converse may not be the true.
2. Every non deterministic finite automaton¹ can be considered to be a transition graph⁴ as well but the converse may not be the true.

Non Deterministic Finite Automaton¹ With Null String² \(\Lambda\)

If \(\Lambda\) is allowed to be an edge in a non deterministic finite automaton¹ then it is called non deterministic finite automaton¹ with \(\Lambda\).
It is a collection of three things:

1. Finite many states with one initial and some final states.
2. Finite set⁵ of inputs, let's say, \(\Sigma =\{a, b, c\}\).
3. There may be more than one transitions for a letter, including \(\Lambda\) or there may not be any transition at all.

Converting into Finite Automaton³ from Non Deterministic Finite Automaton¹

Method 1

Since a non deterministic finite automaton¹ is considered a transition graph,⁴ a corresponding regular epression⁶ can be constructed, using kleene's theorems.⁷
Similarly, a finite automaton³ can be constructed from that regular expression⁶ resulting into an equivalent non deterministic finite automaton.¹

Method 2

For a non deterministic finite automaton,¹ there may be states with no transitions, in correspondence to which we can make finite automaton³ with empty states.
We also have solution for states with multiple transitions.

Example

Following is ournon deterministic finite automaton¹ which needs to be converted

The finite automaton³ which is constructed

References

---

1. Read more about non deterministic finite automaton. ↩↩↩↩↩↩↩↩↩↩↩↩↩

2. Read more about strings. ↩↩

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

4. Read more about transition graph. ↩↩

5. Read more about sets. ↩

6. Read more about regular expressions. ↩↩

7. Read more about kleene's theorems. ↩