HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is relative regularity distinct from regularity?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fromdistinctregularityrelative

Problem

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.

Solution

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.

The answer is no.

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.

This may also provide examples for some of the other points.

Context

StackExchange Computer Science Q#41731, answer score: 2

Revisions (0)

No revisions yet.