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

1.7k Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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

7
On

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.