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
0 comments:
Post a Comment
Let us know your responses and feedback