World's most popular travel blog for travel bloggers.

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

#### 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

#### Post a Comment

Let us know your responses and feedback