Skip to content

Lecture No. 06

Dated: 25-10-2024

Example

Consider a language \(L\) of strings1 such that each one starts and ends with a different letter.

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

CS402_i_6_1.png

Equivalent Finite Automaton

Two finite automata2 which accept the same language are called equivalent finite automata.
The following 3 finite automata are equivalent.
CS402_i_6_2.png
CS402_i_6_3.png
CS402_i_6_4.png
The inputs for these would be \(\Phi\) or \(\{\}\) because there is no final state.
Even if there is, it is impossible to reach.

Example

A language \(L\) defined over \(\Sigma = \{a, b\}\) consisting of strings1 having either triple \(a\) or \(b\).

\[(a + b)^*(aaa + bbb)(a + b)^*\]

CS402_i_6_5.png

References

  1. Read more about strings. ↩↩

  2. Read more about finite automaton. ↩