Lecture No. 17

Dated: 02-11-2024

Method 3

In a non deterministic finite automaton,¹ for a letter, there may be no transition at all or multiple transitions.
The corresponding finite automaton² can be represented as having empty state and having combination of states.

Example

Consider the non deterministic finite automaton¹ which accepts the language containing the string³ \(bb\).

Old States	New Starts After Reading
	a	b
\(z_1^- \equiv x_1\)	\(x_1 \equiv z_1\)	\((x_1, x_2) \equiv z_2\)
\(z_2 \equiv (x_1, x_2)\)	\((x_1, \varnothing) \equiv x_1 \equiv z_1\)	\((x_1, x_2, x_3) \equiv z_3\)
\(z_3^+ \equiv (x_1, x_2, x_3)\)	\((x_1, x_3) \equiv z_4\)	\((x_1, x_2, x_3) \equiv z_3\)
\(z_4^+ \equiv (x_1, x_3)\)	\((x_1, x_3) \equiv z_4\)	\((x_1, x_2, x_3) \equiv z_3\)