3
$\begingroup$

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.

$\endgroup$
3
5
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ @DaniaG. I phrased my answer as a hint deliberately, so I'd appreciate it if you removed that spoiler for future visitors. $\endgroup$
    – Raphael
    Dec 5 '13 at 23:00

Your Answer

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