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$
3
  • $\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
    Commented Jul 16, 2016 at 20:06
  • 2
    $\begingroup$ @Bakuriu You probably meant the opposite of your first sentence. $\endgroup$ Commented Jul 17, 2016 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
    Commented Jul 17, 2016 at 8:17

2 Answers 2

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$
7
  • 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$ Commented Jul 16, 2016 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
    Commented Jul 16, 2016 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$ Commented Jul 16, 2016 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
    Commented Jul 16, 2016 at 22:08
  • 1
    $\begingroup$ @YBerman That sounds right to me. $\endgroup$
    – Owen
    Commented Jul 17, 2016 at 11:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .