Skip to content

Lecture No. 12

Dated: 29-10-2024

Example

CS402_e_12_1.svg
CS402_e_12_2.svg
CS402_e_12_3.svg
CS402_e_12_4.svg
CS402_e_12_5.svg
CS402_e_12_6.svg
CS402_e_12_7.svg

Kleene's Theorem part 3

If the language can be expressed by a regular expression1 then there exists an finite automaton2 accepting the language.

Union of Two Finite Automata2

Imagine you are given 2 regular expressions1 \(r_1\) and \(r_2\) then it is possible to make a finite automaton2 using \(r_1 + r_2\).

Example

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

CS402_e_12_8.svg

\(r_2\)

CS402_e_12_9.svg

\(r_1 + r_2\)

The corresponding finite automaton2 will have initial state which matches the initial state of both previous finite automata.2
Same goes for the final state.

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

CS402_e_12_10.svg

References

  1. Read more about regular expression. ↩↩

  2. Read more about finite automaton. ↩↩↩↩↩