patternMinor
Is relative regularity distinct from regularity?
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 $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.
$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.
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.