Lecture No. 14

Dated: 29-10-2024

Closure of a Finite Automaton¹

It is concatenation of a finite automaton¹ with itself.
The initial state is also the final state.

Example

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

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

Oldstate	New state after reading
	a	b
\(z_1^\pm \equiv x_1\)	\(x_1 \equiv z_2\)	\((x_2, x_1) \equiv z_3\)
\(z_2 \equiv x_1\)	\(x_1 \equiv z_2\)	\((x_2, x_1) \equiv z_3\)
\(z_3^+ \equiv (x_2, x_1)\)	\(x_1 \equiv z_2\)	\((x_2, x_1) \equiv z_3\)

Example

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

Old States	New States after reading
	a	b
\(z_1^\pm \equiv y_1\)	\(y_2 \equiv z_3\)	\(y_1 \equiv z_2\)
\(z_2 \equiv y_1\)	\(y_2 \equiv z_3\)	\(y_1 \equiv z_2\)
\(z_3 \equiv y_2\)	\((y_3, y_1) \equiv z_4\)	\(y_1 \equiv z_2\)
\(z_4^+ \equiv (y_3, y_1)\)	\((y_3, y_1, y_2) \equiv z_5\)	\((y_3, y_1) \equiv z_4\)
\(z_5^+ \equiv (y_3, y_1, y_2)\)	\((y_3, y_1, y_2) \equiv z_5\)	\((y_3, y_1) \equiv z_4\)

References

---

1. Read more about finite automaton. ↩↩