# How do you find an infinite regular language that is a subset of a non-regular language?

In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't know how to construct one.

• Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. – D.W. Feb 8 '16 at 21:27
• Every non-regular language is infinite, because every finite language is regular. – rici Feb 8 '16 at 21:41

A general aproach consist in making a non-regular language by the union of a regular language with a language that is known to be non-regular and then prove that the resulting language is irregular by using the closure property of intersection between regular languages. For example as Anton said if you construct $L= \mathscr{L}(a^*)\cup \{a^nb^n : n\geq0\}$ then $L$ is irregular(can be proved using the closure property) and $\mathscr{L}(a^*)$ is regular as requested.

But you have to be carefull. You can choose two languages with a regular union. For example:

$L= \mathscr{L}(a^*b^*)\cup \{a^nb^n : n\geq0\}=\mathscr{L}(a^*b^*)$ is regular.

Here $\mathscr{L}(a^*b^*)$ overrides the non-regular language. This can be easily corrected by choosing a better non-regular language:

$L= \mathscr{L}(a^*b^*)\cup \{a^nb^nc^n : n\geq0\}$ is non-regular.

• Recipe: pick the non-regular partner so that the union is disjoint. Then the closure-properte proof always works. (Or does it?) – Raphael Feb 9 '16 at 8:25
• Note that in the examples $\mathscr{L}(a^*)$ and $\{a^nb^n:n\geq 0\}$ aren't entirely disjoint. They share the word $\epsilon$. I would say that the languages have to be "sufficient disjoint" to make sure that the intersection will recover the known non-regular language. – Renato Sanhueza Feb 9 '16 at 17:53
• The closure-property proof always works if the intersection of a non-regular language $N$ and its regular partner $R$ is regular (e.g. finite as in the two answers here or empty as @Raphael mentioned). Too see this one can use a "test" regular language $R_T = \overline{R} \cup (R \cap N)$ [this is where we want $R \cap N$ to be regular] and an equation $(R \cup N) \cap R_T = N$ to prove $(R \cup N)$ is regular. – Anton Trunov Feb 9 '16 at 19:51
• @AntonTrunov nice catch! – Renato Sanhueza Feb 9 '16 at 21:19

Note that any non-regular language is infinite, since any finite language is regular.

Instead of searching for infinite regular subset in some given non-regular language, why don't we try to construct a non-regular language that contains an infinite regular language?

To do that we can take some context-free language, which is not regular, e.g. classical $a^nb^n, n \ge 0$, and "add" some infinite regular language to it. By "add" I mean the union operation on sets.

I should notice that one has to be careful while "adding" an infinite regular language to a non-regular one, since $L(a^nb^n) \cup \Sigma^* = \Sigma^*$, which is obviously regular.

So let's take a regular language $L(a^*)$, which has only one string in common (the empty string) with $L(a^nb^n), n \ge 0$ as our candidate "addition".

It's easy to prove the language $L(a^*) \cup L(a^nb^n), n \ge 0$ is non-regular (context-free). And its regular subset $L(a^*)$ is infinite.