# Is relative regularity distinct from regularity?

Let $L$ and $G$ be languages over a finite alphabet $\Sigma$. $L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input in $G \setminus L$; the behaviour of the automaton on inputs in $\Sigma^{*}\setminus G$ is not specified. Here are some simple facts about relative regularity.

• If $G$ is regular, then so is any $L$ that is regular relative to $G$.
• If $L$ is regular then it is also regular relative to any $G \subseteq \Sigma^{*}$ in which it is contained.
• If $L \subseteq G$ and $G \setminus L$ is regular then $L$ is regular relative to $G$.
• It is possible that $L$ is regular and regular relative to $G$, but $G$ is not regular. (Let $\Sigma = \{0,1\}$, $L = \emptyset$ and take $G$ to be some non-regular language such as the palindromes.)
• It is possible that $L$ and $G$ are not regular but $L$ is regular relative to $G$. (Just take $G=L$.)
• $L$ is regular relative to $G$ iff $L \subseteq G$ and there is some language $S \subseteq \Sigma^{*}\setminus G$ such that $L \cup S$ is regular.

If $L$ is regular relative to some $G \subseteq \Sigma^{*}$, and $G \setminus L$ is not a regular language, is $L$ always regular?

That last fact suggests that the answer should be no, but I can't think of a counterexample.

If this is a standard exercise or the concept has a name then I would appreciate a pointer.

How about $G = \{ a^n b^n : n \geq 0 \}$ and $L = \{ a^{2n} b^{2n} : n \geq 0 \}$?

Can't you define it as: $L$ is regular relative to $G$ iff there is a regular language $R$ such that $L=G\cap R$.

If I am correct, it seems more easily understood, more visual.

The essence of what you are asking is then: when you partition a language by intersection with a regular set, is the regularity of one part related in any way to the regularity of the other part.

Consider the alphabet $\Sigma$ not containing the symbols $a$ and $b$, and two languages $G_1, G_2 \subset \Sigma^*$. Let $G=aG_1 \cup bG_2$ and $L=aG_1$, so that $G\setminus L=bG_2$.
The language $L$ is regular relative to $G$, with the discriminating regular language $R=a\Sigma^*$.
But $G_1$ and $G_2$ are whatever you want them to be, and prefixing with $a$ or $b$ usually does not change it much, with regard to most families of languages.