Hot answers tagged


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 ...


Recall that all regular langauges satisfy the pumping lemma, which we capture by the following informal proposition: $$\text{regular}\implies\text{pumping lemma}.$$ Applying modus tollens (a.k.a. contrapositive), we get $$\neg\text{pumping lemma}\implies\neg\text{regular}.$$ Therefore, to prove a language is not regular, it suffices to show that it does not ...

Only top voted, non community-wiki answers of a minimum length are eligible