I am just curious is there any non regular language whose subset is regular?
Is there a subset of a non regular language that is regular
-
0@piperchester This comment is very old and it seems I deleted the file from my Dropbox - luckily I have an updated version. You will find the mentioned overview of languages on the last page of my [cheatsheet](http://www.christian-ivicevic.com/Files/Theo15/Cheatsheet.pdf). – 2015-09-23
3 Answers
The empty language is a regular subset of any language at all.
More generally, every finite subset of any language is regular.
For example, let $L$ be the language $\{ a^n | n\text{ is prime} \} = \{ aa, aaa, aaaaa, a^7, \ldots\}$. Let $R$ be the subset of $L$ consisting just of $\{ aa, aaaaa, a^{11}, a^{109} \}$. Then $L$ is not regular, but $R$ is.
-
0Every finite set is regular. http://math.stackexchange.com/questions/216047/formally-prove-that-every-finite-language-is-regular/216075#216075 – 2012-11-13
You are looking for regular "within" non-regular. Not an answer, but related, and more amusing is the following.
There operations on languages that (however complex the language) yield a regular language. As an example there is the operator "all subsequences" (sometimes called "sparse subwords"). Starting with $\{ a^n b^{n^2}\mid n\ge 1\}$ we get $a^* b^*$.
Shallit (in his book second course in formal language theory) starts with the languages of primes in ternary notation $\{ 2,10,12,21,102,111,122,201,212,1002,\dots\}$, and shows this gives the subsequence language $\Sigma^*2\Sigma^* \cup \Sigma^*1\Sigma^*0\Sigma^* \cup \Sigma^*1\Sigma^*1\Sigma^*1\Sigma^*$, $\Sigma = \{0,1,2\}$.
Nice, huh?
For example {a^n b^n| n>=0} is a non-regular language, but it has infinite number of subsets that are regular languages: 1) the empty set, 2) {lambda} 3) {ab} 4) {a^2 b^2} . . . and any finite combinations of these languages.