5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This seems like a productive rephrasing of the last property. $\endgroup$ – András Salamon Apr 23 '15 at 12:22
  • $\begingroup$ @AndrásSalamon I do not know if this makes sense. I have a near biological graphic vision of language intersections, where the properties of (part of) the dividing line segments are set by automata (as some cell properties are defined by molecules on the external membrane). But each fragment of that line can independently involve a different (family of) automaton (as many molecules or tunnels can be on cellular skin). Together they define the properties of the enclosed language. Membranes of G can have different molecules inside and outside R, which has only regular ones on its skin. $\endgroup$ – babou Apr 23 '15 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.