Lecture No. 10

Dated: 26-10-2024

Example

Consider a language \(L\) defined over \(\Sigma = \{a, b\}\) containing \(aa\) or \(bb\).

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

Non Determinism

It is possible that for a certain string,¹ there may not be any path or there may be multiple paths.
This causes non determinism.
Though it can help differentiating between finite automata² from transition graphs³ and generalized transition graphs⁴ since finite automa² are also called deterministic finite automata.

Kleene's Theorem

If a language can be represented by either

1. A finite automaton²
2. A transition graph³
3. A regular expression⁵

Then it can be represented by other 2 as well.

This theorem can be proved by following arguments

1. If a language is represented by finite automaton² then it can be represented by a transition graph³ as well since every finite automaton² is a transition graph³
2. If a language is represented by transition graph³ then it can be represented by a regular expression⁵ as well
3. If a language is represented by a regular expression⁵ then it can be represented by a finite automaton² as well.

References

---

1. Read more about strings. ↩

2. Read more about finite automata. ↩↩↩↩↩↩

3. Read more about transition graph. ↩↩↩↩↩

4. Read more about generalized transition graph. ↩

5. Read more about regular expressions. ↩↩↩