Proving Nonregularity Using Closure Properties

Hello. In the previous lesson, you used the pumping lemma to prove that

$$\{0^n{1}^n\mid n\ge 0\}$$

is not regular. That result is more valuable than a single example: it is now a known nonregular language that can serve as a contradiction target.

This lesson develops a second proof strategy. Rather than searching for a string that breaks the pumping lemma, we temporarily assume an unfamiliar language is regular, apply a closure property, and derive that a language already known to be nonregular would have to be regular. The contradiction rules out the original assumption.

---

The central logic: closure properties used backward

A closure property says that applying a particular operation to regular languages produces another regular language. From the previous lesson, you have already seen why regular languages are closed under intersection: a product DFA can track membership in two regular languages simultaneously.

For example:

• If $L$ and $R$ are regular, then $L\cap R$ is regular.
• If $L$ is regular over alphabet $\Sigma$, then its complement $\overline{L}={\Sigma }^{\ast }\setminus L$ is regular.

A closure-property nonregularity proof uses these facts in a contradiction argument:

1. Identify a language $K$ that is already known to be nonregular.
2. Suppose the target language $L$ were regular.
3. Combine $L$ with one or more known regular languages, or take its complement.
4. Use closure to conclude that the resulting language must be regular.
5. Prove that the result is exactly $K$.
6. Contradict the known fact that $K$ is nonregular.

The essential asymmetry is worth stating carefully:

Regular languages are closed under operations such as intersection and complement. Nonregular languages are not “closed” in the same way.

For instance, two nonregular languages can have a regular intersection. The method never claims otherwise. It assumes the unknown target is regular and uses closure to force a contradiction.

The image’s key idea is that the known nonregular language appears at the end of the argument, as an impossible consequence of the assumption that the unknown language is regular.

---

Complementation: flipping membership

Fix an alphabet $\Sigma$. The complement of a language $L$ is always relative to that alphabet:

$$\overline{L}={\Sigma }^{\ast }\setminus L.$$

Thus, a string belongs to $\overline{L}$ exactly when it is a string over $\Sigma$ that does not belong to $L$.

Why is complement closure true? If a DFA $M$ recognizes $L$, keep its states, start state, alphabet, and transitions unchanged, but swap accepting and rejecting states. Because a DFA ends in exactly one state after reading any input, the modified DFA accepts precisely the strings that $M$ rejects.

This has a useful consequence. If $K$ is known to be nonregular, then $\overline{K}$ is also nonregular. Indeed, if $\overline{K}$ were regular, complement closure would make

$$\overline{\overline{K}}=K$$

regular, a contradiction.

Example: nonpalindromes

Let

$$\mathrm{PAL}=\{w\in \{0,1{\}}^{\ast }\mid w=w^R\},$$

where $w^R$ is the reversal of $w$. Suppose it is already known that $\mathrm{PAL}$ is nonregular.

Now define

$$N=\{w\in \{0,1{\}}^{\ast }\mid w\ne w^R\}.$$

This is the language of binary strings that are not palindromes. Since every binary string either is or is not a palindrome,

$$N=\overline{\mathrm{PAL}}.$$

To prove that $N$ is nonregular, write the argument explicitly:

Assume, for contradiction, that $N$ is regular. By closure of regular languages under complement, $\overline{N}$ is regular. But $\overline{N}=\mathrm{PAL}$, and $\mathrm{PAL}$ is known to be nonregular. This is a contradiction. Therefore $N$ is not regular.

Notice that this proof does not need a pumping length, a special string, or cases for possible decompositions. All the work lies in recognizing the complement relationship and fixing the alphabet correctly.

---

Intersection as a regular filter

Intersection is often the most flexible closure tool. Think of a known regular language $R$ as a filter: it keeps only the strings of the target language $L$ that have a controlled form. If that filtered portion is a known nonregular language, then $L$ cannot have been regular.

The most common filter is

$$0^{\ast }{1}^{\ast }.$$

It is regular because it is described by a regular expression. It contains strings consisting of any number of zeros followed by any number of ones, including $ϵ$, $000$, and $1111$. It excludes strings such as $101$ and $0100$, whose symbols alternate or return to zeros after a one.

---

A complete intersection proof

Consider the language

$$E=\{w\in \{0,1{\}}^{\ast }\mid {\#}_0(w)={\#}_1(w)\},$$

where ${\#}_0(w)$ and ${\#}_1(w)$ denote the number of zeros and ones in $w$, respectively.

Unlike

$$\{0^n{1}^n\mid n\ge 0\},$$

the language $E$ allows symbols in any order. For example, $0101$, $1100$, and $0011$ all belong to $E$. We will prove that $E$ is nonregular by filtering it with $0^{\ast }{1}^{\ast }$.

Let

$$R=0^{\ast }{1}^{\ast }.$$

The crucial identity is

$$E\cap R=\{0^n{1}^n\mid n\ge 0\}.$$

Do not merely assert this equality: proving it is the core of the argument.

Why the equality holds

Take any string $w\in E\cap R$. Since $w\in R$, it has the form

$$w=0^i{1}^j$$

for some $i,j\ge 0$. Since $w\in E$, it has equally many zeros and ones. Therefore $i=j$. Letting this common value be $n$, we get

$$w=0^n{1}^n.$$

This proves that every string in $E\cap R$ belongs to $\{0^n{1}^n\mid n\ge 0\}$.

Conversely, every string $0^n{1}^n$ has equal numbers of zeros and ones, so it belongs to $E$; it also has all zeros before all ones, so it belongs to $R$. Thus it belongs to $E\cap R$.

Both inclusions have been established, so the identity follows.

The proof

Claim: $E$ is not regular.

Proof: Assume, toward a contradiction, that $E$ is regular. The language

$$R=0^{\ast }{1}^{\ast }$$

is regular. Because regular languages are closed under intersection, $E\cap R$ is regular.

But

$$E\cap R=\{0^n{1}^n\mid n\ge 0\}.$$

The language on the right is nonregular, as established with the pumping lemma in the previous lesson. This contradicts the conclusion that $E\cap R$ is regular. Therefore $E$ is not regular. $\square$

The regular filter does two jobs at once:

• It discards complicated orderings such as $0101$.
• It preserves exactly the structured subset in which equal counts become the known nonregular pattern $0^n{1}^n$.

---

Choosing an effective regular filter

The intersection method is not based on the fact that a language has a nonregular-looking subset. That reasoning would be invalid: a regular language may contain nonregular subsets. For example,

$$0^{\ast }{1}^{\ast }$$

is regular but contains the nonregular subset

$$\{0^n{1}^n\mid n\ge 0\}.$$

What makes the closure proof work is the conditional claim:

If the target $L$ were regular, then its intersection with the independently known regular filter $R$ would be regular.

A good filter is therefore chosen to make an exact identity of the form

$$L\cap R=K$$

easy to prove, where $K$ is a known nonregular language.

When designing a proof, use this checklist:

Step	What to establish
Select a seed	Name a language $K$ already known to be nonregular.
State the assumption	Assume the target language $L$ is regular.
Choose a legal operation	Typically intersect $L$ with a language $R$ that is clearly regular, or complement $L$.
Invoke closure correctly	Under the assumption, the constructed language is regular.
Prove an exact identity	Show that the constructed language equals $K$, usually with two set inclusions.
State the contradiction	The same language would be regular and nonregular. Conclude that $L$ is nonregular.

Two common flaws are especially important to avoid:

1. Using a nonregular auxiliary language.
   To invoke intersection closure, every input language must be regular under the assumption. The filter $R$ must therefore be independently known to be regular.

2. Showing only containment rather than equality.
   Knowing that $K\subseteq L\cap R$ does not produce a contradiction. A regular language can contain a nonregular subset. You need an exact characterization of $L\cap R$, or another argument that directly identifies a known nonregular result.

---

Key takeaways

Closure properties offer a way to transfer a known nonregularity result to a new language. The proof begins by assuming the target is regular, not by assuming anything about the known nonregular seed.

For complement proofs, specify the alphabet and identify the complement exactly. For intersection proofs, select a regular filter that isolates a known nonregular language, then prove the resulting set equality in both directions.

You now have two complementary methods for proving nonregularity: the pumping lemma, which exposes a forbidden pumping behavior directly, and closure arguments, which reduce the target language to a nonregular language you already understand. Next, the course turns to Myhill–Nerode distinguishability, a state-based method for proving that any DFA for a language would require arbitrarily many states.