Lecture No. 24
Dated: 23-02-2025
Regular Languages
Read about regular languages.
By Regular Expressions
Read about regular expressions.
By Transition Graphs
Read about transition graphs and Kleene's theorem.
Example
Consider 2 transition graphs1
Transition graph1 of \(L_1 + L_2\).
Transition graph1 of \(L_1L_2\).
Transition graph1 of \(L_2^*\).
Complement of a Language
If \(L\) is a language2 defined over \(\Sigma\) then the language2 made out of strings2 which are also defined over \(\Sigma\) but are not present in \(L\) is called the complement of language2 \(L\).
It is denoted as \(L^c\) or \(L^\prime\).
Theorem
Statement
If \(L\) is a regular language3 then \(L^c\) is also a regular language.3
Proof
If \(L\) is a regular language,3 that means it can be represented by a regular expression4 which further means, it can be represented by a finite automaton5
(by Kleene's theorem6).
After converting to finite automaton5 we can make the final states as non-final and non-final states as final ones. This new finite automaton5 now represents \(L^c\).
It can again, be represented by a regular expression4 (by Kleene's thoerem6) which makes it a regular language.3
Example
Let \(L\) be a language over alphabet \(\Sigma = \{a, b\}\) consisting of only 2 words, \(aba\) and \(abb\).
Finite automaton5 of \(L\).
Finite automaton5 of \(L^c\).
Theorem
Statement
If \(L_1\) and \(L_2\) are 2 regular languages,3 then \(L_1 \cap L_2\) is also a regular language.3
Proof
Using De Morgan's law,
If \(L_1\) and \(L_2\) are regular languages3 then \(L_1^c\) and \(L_2^c\) are also regular languages,3 which means \(L_1^c \, \cup \, L_2^c\) is also regular language,3 which further implies that \((L_1^c \, \cup \, L_2^c)^c\) is also a regular language.3