# Prove the existence of regular $C$ so that: $A \prec C \prec B$

Given $A,B$ regular languages with $A \prec B$. Prove the existence of $C\in L_{\text{regular}}$ so that: $A \prec C \prec B$.

Here, $A\prec B$ stands for: $A\subset B$ and $B\setminus A$ is infinite.

I tried to go for: $C=\overline{B} \cup A$ and some other options but it didn't work out.

• Study the answer to the recent question How can i partition an infinite regular language into 2 strange infinite regular languages?. Dec 5 '13 at 16:11
• Where did the comments go? You cannot prove that $C$ exists without some conditions on $A$ and $B$. Dec 6 '13 at 1:24
• @DavidRicherby You are right. The question was edited so that $A \prec B$ is also given, now it's correct.
– user11841
Dec 6 '13 at 1:45

Hint: Note that $B \setminus A$ is regular by closure properties of $\mathsf{REG}$.
Since $B \setminus A$ is also infinite, you can find an infinite language $D \in \mathsf{REG}$ so that $D \prec B \setminus A$.