Skip to content

Lecture No. 25

Dated: 01-03-2025

Theorem

Statement

If \(L_1\) and \(L_2\) are two regular languages1 then \(L_1 \cap L_2\) is also a regular language.1

Proof

Using De Morgan's law

\[(L_1^c \, \cup \, L_2^c)^c = (L_1^c)^c \, \cup \, (L_2^c)^c = L_1 \, \cap \, L_2\]

Example

\[L_1 = \text{language of words with double a's}\]
\[L_2 = \text{language of words with even number of a's}\]

cs402_e_25_1.svg

Finite Automaton2 for \(L_1\).

cs402_e_25_2.svg

Finite Automaton2 for \(L_2\).

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

cs402_e_25_3.svg

Finite Automaton2 for \(L_1^c\).

cs402_e_25_4.svg

Finite Automaton2 for \(L_2^c\).

Old States New States After Reading
a b
\(z_1 \pm \equiv (p, 1)\) \((q, 2) \equiv z_4\) \((p, 1) \equiv z_1\)
\(z_2 + \equiv (p, 2)\) \((q, 1) \equiv z_3\) \((p, 2) \equiv z_2\)
\(z_3 + \equiv (q, 1)\) \((r, 2) \equiv z_6\) \((p, 1) \equiv z_1\)
\(z_4 + \equiv (q, 2)\) \((r, 1) \equiv z_6\) \((p, 2) \equiv z_2\)
\(z_5 \equiv (r, 1)\) \((r, 2) \equiv z_6\) \((r, 1) \equiv z_6\)
\(z_6 + \equiv (r, 2)\) \((r, 1) \equiv z_5\) \((r, 2) \equiv z_6\)

cs402_e_25_5.svg

Finite Automaton2 for \(L_1^c \, \cup \, L_2^c\).

cs402_e_25_6.svg

Finite Automaton2 for \(L_1 \, \cap \, L_2\).

Determining Regular Expression3

cs402_e_25_7.svg

Eliminating states \(z_2\) and \(z_6\) from \(L_1 \, \cap \, L_2\).

cs402_e_25_8.svg

Eliminating states \(z_2\) and \(z_6\) from \(L_1 \, \cap \, L_2\).

Non Regular Languages

The languages which cannot be expressed using regular expressions3 are called non regular languages.

Example

  • Palindrome
  • Prime numbers

Note

A non regular language cannot be expressed by a finite automaton2 or a transition graph.4

Example

Imagine a language5 \(L\).

\[L = \{a^nb^n: n \in \mathbb W\}\]

Assume that \(L\) is a regular language1 and can be represented by a finite automaton.2 The finite automaton2 has a limited number of states. \(L\) will have words with length that is greater than the number of states in the finite automaton.2 This means that for finite automaton2 to represent \(L\), it needs to have a circuit.

cs402_e_25_9.svg

Finite automaton2 with 10 states for \(a^9b^9\).

Notice how this finite automaton2 is also capable of generating words such as \(a^{9+4}b^9\). More generally, \(a^9(a^4)^mb^9(b^2)^n\) where \(m, n \in \mathbb W\). These are not words belonging to \(L\).

References

  1. Read more about regular languages. ↩↩↩

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

  3. Read more about regular expressions. ↩↩

  4. Read more about transition graph. ↩

  5. Read more about the foundations. ↩