3.Using Closure Properties§

Using closure properties of regular languages, construct a language that should be regular, but for which you have already shown is not regular. Contradiction.

Proof Outline:
Assume \(L\) is regular.
Apply closure properties to \(L\) and other regular languages, constructing \(L'\) that you know is not regular.
Closure properties \(\Rightarrow L'\) is regular.
Contradiction. So \(L\) is not regular.

Example

Prove that \(L = \{a^3b^nc^{n-3} | n > 3 \}\) is not regular.
Assume \(L\) is regular.
Define a homomorphism \(h: \Sigma \rightarrow \Sigma^*\) such that \(h(a) = a\quad |\quad h(b) = a\quad |\quad h(c) = b\).
\(h(L) = \{a^3a^nb^{n-3} | n > 3 \} = \{a^{n+3}b^{n-3} | n > 3\}\)
\(L\) is regular and closure under homomorphism \(\Rightarrow h(L)\) is regular.
The language \(\{b^6\}\) is a regular language.
By closure under concatenation, \(L' = h(L)\{b^6\} = \{a^{n+3}b^{n+3} | n > 3\}\) is regular.
The language \(L'' = \{ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb, aaaaaabbbbbb\}\) is regular.
By closure under union, \(L' \cup L'' = \{a^nb^n | n > 0\}\) is regular.
But, we showed earlier that \(\{a^nb^n | n > 0 \}\) is not regular! Contradiction.

Example

Prove that \(L = \{a^nb^ma^{m}\ |\ m \ge 0, n \ge 0 \}\) is not regular.
Assume \(L\) is regular.
\(L1 = \{ bb^{*}aa^{*}\}\)
\(L2 = L \cap L1 = \{b^na^n \mid n > 0\}\)
Define a homomorphism \(h: \Sigma \rightarrow \Sigma^*\) such that \(h(a) = b\quad |\quad h(b) = a\).
\(h(L2) = \{a^nb^n | n>0 \}\) should be regular.
We showed earlier that \(\{a^nb^n | n > 0 \}\) is not regular. Contradiction.

Example

Prove that \(L_1 = \{a^nb^na^n\ |\ n > 0\}\) is not regular.
Assume \(L_1\) is regular.
The goal is to try to construct \(\{a^nb^n | n > 0\}\) which we know is not regular.
NOTE: Trying to intersect with \(\{a^{*}b^{*} \}\) does not work.
Let \(L_2 = \{a^{*}\}\). \(L_2\) is regular.
By closure under right quotient, \(L_3 = L_1 \backslash L_2 = \{a^nb^na^p | 0 \le p \le n, n > 0\}\) is regular.
By closure under intersection, \(L_4 = L_3 \cap \{a^{*}b^{*}\} = \{a^nb^n | n > 0\}\) is regular.
We already proved that \(L_4\) is not regular. Contradiction.

Things to Think About

Is every language either regular or not regular?
Regardless of “truth”, can we know for every language if it is regular or not regular?
There are more infinite sets of strings than there are finite sets of strings.
(Really? Aren’t there an infinite number of finite sets of strings?)
Since any “description” of a language (as a RegEx, in English, as a DFA) is ultimately a string, that means there are more languages than we can describe!