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 ⇒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:Σ→Σ∗
such that h(a)=a|h(b)=a|h(c)=b.
h(L)={a3anbn−3|n>3}={an+3bn−3|n>3}
L is regular and closure under homomorphism
⇒h(L) is regular.
The language {b6} is a regular language.
By closure under concatenation,
L′=h(L){b6}={an+3bn+3|n>3}
is regular.
The language
L″ 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!