There exists a regular language A such that for all languages B, A ∩ B is regular.

There exists a regular language A such that for all languages B, A ∩ B is regular.

The above given statement is true but I couldn't make any proof or find any proof. It is an objective type question asked here to find whether the given statement is true or false. I want to know how to conclude this given statement is true.

• There exists infinite regular languages $A$ such that for all languages $B$, $A \cap B$ is regular. Take any finite $A \subseteq \Sigma^*$. – Bakuriu Jul 16 '16 at 20:06
• @Bakuriu You probably meant the opposite of your first sentence. – 6005 Jul 17 '16 at 0:16
• @6005 It depends on how you parse that sentence. It should be read as $\exists^{\infty} A ....$ (there exist an infinite number of languages $A$ such that) not $\exists A, |A|=\infty ...$ (there exists one language, which is infinite, ..) – Bakuriu Jul 17 '16 at 8:17

Yes, that's true. Consider $A=\emptyset$ (which is regular), then $\emptyset \cap B=\emptyset$ (which is regular).

If $A$ is a finite language, then it is regular and meets your condition.

On the other hand if $A$ is any infinite regular language, since it is countably infinite ($\aleph_0$) it will contain $\aleph_1$ sublanguages. Every regular language is defined by a finite regular expression (of which there are $\aleph_0$) so there will be sublanguages of $A$ which is not regular.

So finiteness is necessary and sufficient.

• Note that your answer depends on the continuum hypothesis. You probably just meant "uncountably many" which is all you need for your argument, but without irrelevant assumptions, you would have $2^{\aleph_0}$ sublanguages. – Richard Rast Jul 16 '16 at 15:42
• Rule of thumb: Unless you're playing around with the CH or the ordinals, you want either beth numbers or some expression involving $\aleph_0$. – Kevin Jul 16 '16 at 16:27
• @Richard: Or simply ‘at least $\aleph_1$’, though I too would prefer ‘uncountably many’ here, since that gets directly to the essential point. – Brian M. Scott Jul 16 '16 at 20:14
• As a constructive way to make a nonregular sublanguage, take all the sentences, order them by length, then take a subsequence where the length grows too quickly to be regular. – Owen Jul 16 '16 at 22:08
• @YBerman That sounds right to me. – Owen Jul 17 '16 at 11:32