Is relative regularity distinct from regularity?

Problem Detail: 

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.

Asked By : András Salamon

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41731

3200 people like this

 Download Related Notes/Documents