# Prove that every regular subset of $a^nb^n$ is finite

How to prove that every regular subset of $$L=\{a^nb^n \mid n\ge0 \}$$ is finite?

I know that every finite language is regular, and it's not true that every regular language is finite.

I also know that $$a^n b^n$$ is non-regular language.

I can find examples of finite regular subsets of $$L$$, for example $$\{\epsilon, ab, aabb\}$$, but how do I prove that all regular subsets of $$T$$ are finite?

• Your question doesn’t make sense. What is “a regular language in language L” supposed to mean? Jun 26 '20 at 10:06
• (If something looks too obvious to prove, try contradiction.) Jun 26 '20 at 22:28

This is a simple application of the pumping lemma. Suppose that $$L'$$ is an infinite subset of $$L$$. Given $$p$$, since $$L'$$ is infinite, there exists some $$n \geq p$$ such that $$w = a^nb^n \in L'$$. Let $$w = xyz$$ be a decomposition of $$w$$ such that $$|xy| \leq p$$ and $$y \neq \epsilon$$. Then $$y = a^t$$ for some $$t \neq 0$$, and so $$xy^0z = a^{n-t}b^n \notin L'$$. Therefore $$L'$$ is not regular.

One might be tempted to think that this argument generalizes to every $$L$$ whose non-regularity can be proved using the pumping lemma. However, this is incorrect, as the example of $$L \cup c^*$$ shows.

This raises the following intriguing question:

For which infinite languages $$L$$ is it the case that all regular subsets of $$L$$ are finite?

• My guess to answer your question: if none of the strings are pumpable, so if each string of $L$ can be used with the pumping lemma to show $L$ irregular. If any string of $L$ is pumpable, then all its pumps form a regular subset. Jun 26 '20 at 12:01

Prove that if your language contains $$a^nb^n$$ and $$a^mb^m$$ for n <> m then after parsing $$a^n$$ and parsing $$a^m$$ you end up in different states. (Proof is trivial).

If there are infinitely many different n, m then the number of states cannot be finite.