Every non-regular language has a subset which is a regular language?

Question

Could anyone give me a counterexample so as to understand the proof? Thanks in advance

Answer 1

Your claim is true, so there is no counterexample. $\emptyset$ is a regular language and is a subset of every (non-regular) language.

Answer 2

In order to make the question more interesting, let us ask for the regular subset to be infinite.

Here is an example of an infinite language with no infinite regular subset: $$ \{ a^{n^2} : n \geq 0 \}. $$ Indeed, suppose that $L$ is an infinite subset of this language which is regular. Let $p$ be the pumping length of $L$. Since $L$ is infinite, there is a word $a^{n^2} \in L$ such that $n \geq p$. The pumping lemma gives us a decomposition $a^{n^2} = xyz$ with $|xy| \leq p \leq n$ and $y$ non-empty. Then $xy^2z = a^{n^2+m}$, where $1 \leq m \leq n$. Since $n^2 < n^2+m < n^2 + 2n + 1 = (n+1)^2$, we know that $xy^2z \notin L$, contradicting the pumping lemma. Thus $L$ is not regular.

More generally, if $\mathcal{A} = \{ A_n : n \in \mathbb{N} \}$ is any countable collection of infinite languages, then we can construct an infinite language $L$ such that no language in $\mathcal{A}$ is a subset of $L$. The construction is iterative. We will construct finite sets $L^+_n,L^-_n$, starting with $L^+_0 = L^-_0 = \emptyset$. Given $L^+_n,L^-_n$, we construct $L^+_{n+1},L^-_{n+1}$ as follows. First, choose some $w_n \in A_n \setminus L_n^+$; this is possible since $A_n$ is infinite. Let $L^-_{n+1} = L^-_n \cup \{ w_n \}$. Second, choose some $x_n \notin L^+_n \cup L^-_{n+1}$, and let $L^+_{n+1} = L^+_n \cup \{ x_n \}$. Finally, take $L = \bigcup_{n \geq 0} L^+_n$. Since all $x_n$ are different, $L$ is infinite. Since $w_n \notin L$, we know that $L \neq A_n$.