5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There exists infinite regular languages $A$ such that for all languages $B$, $A \cap B$ is regular. Take any finite $A \subseteq \Sigma^*$. $\endgroup$ – Bakuriu Jul 16 '16 at 20:06
  • 2
    $\begingroup$ @Bakuriu You probably meant the opposite of your first sentence. $\endgroup$ – 6005 Jul 17 '16 at 0:16
  • 4
    $\begingroup$ @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, ..) $\endgroup$ – Bakuriu Jul 17 '16 at 8:17
27
$\begingroup$

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

$\endgroup$
25
$\begingroup$

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.

$\endgroup$
  • 14
    $\begingroup$ 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. $\endgroup$ – Richard Rast Jul 16 '16 at 15:42
  • 2
    $\begingroup$ 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$. $\endgroup$ – Kevin Jul 16 '16 at 16:27
  • 3
    $\begingroup$ @Richard: Or simply ‘at least $\aleph_1$’, though I too would prefer ‘uncountably many’ here, since that gets directly to the essential point. $\endgroup$ – Brian M. Scott Jul 16 '16 at 20:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Owen Jul 16 '16 at 22:08
  • 1
    $\begingroup$ @YBerman That sounds right to me. $\endgroup$ – Owen Jul 17 '16 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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