Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am just curious is there any non regular language whose subset is regular?

share|cite|improve this question
Sure, any finite subset of a language is regular. Or the set of palindromes in $\{a,b\}$ is irregular but the set of palindromes in one letter is regular, if you need an infinite example. – Thomas Andrews Nov 13 '12 at 18:23
@Thomas what do you mean by a set of palindromes in one letter. Can u give an example – user34790 Nov 13 '12 at 18:25
Palindromes in one letter are just any $a*$ or $b*$. Basically, any word with only one letter is a palindrome. – Thomas Andrews Nov 13 '12 at 18:25
Ouch! You've asked 21 questions, and accepted only a handful of answers. If you have received answers which have been particularly helpful, please take the time to show appreciation by accepting such answers. – amWhy Nov 13 '12 at 18:37
I can provide a cheat sheet from my "Theoretical Computer Science" course (in German). Just have a look at the top picture with all the boxes. From top to bottom (on thr right hand side) the descriptions are: all languages $\Sigma^*$, semi-decidable (Type 0), decidable, LOOP-decidable, NP, P, context free (Type 2), regular (Type 3), finite. Hope this might help :) – Christian Ivicevic Nov 13 '12 at 18:53

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.

share|cite|improve this answer
Can u give an example? – user34790 Nov 13 '12 at 18:25
@user34790: Every finite language is regular because you can create a enumerate all elements extensionally. Furthermore there exists a regular expression of the form "word1 | word2 | ... | wordN" which implies the regularity of all finite languages. – Christian Ivicevic Nov 13 '12 at 18:56
@MJD How is R regular? – user34790 Nov 13 '12 at 19:57
Every finite set is regular.… – MJD Nov 13 '12 at 20:03

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?

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.