0
$\begingroup$

In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't know how to construct one.

$\endgroup$
  • 1
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. $\endgroup$ – D.W. Feb 8 '16 at 21:27
  • 1
    $\begingroup$ Every non-regular language is infinite, because every finite language is regular. $\endgroup$ – rici Feb 8 '16 at 21:41
2
$\begingroup$

A general aproach consist in making a non-regular language by the union of a regular language with a language that is known to be non-regular and then prove that the resulting language is irregular by using the closure property of intersection between regular languages. For example as Anton said if you construct $L= \mathscr{L}(a^*)\cup \{a^nb^n : n\geq0\}$ then $L$ is irregular(can be proved using the closure property) and $\mathscr{L}(a^*)$ is regular as requested.

But you have to be carefull. You can choose two languages with a regular union. For example:

$L= \mathscr{L}(a^*b^*)\cup \{a^nb^n : n\geq0\}=\mathscr{L}(a^*b^*)$ is regular.

Here $\mathscr{L}(a^*b^*)$ overrides the non-regular language. This can be easily corrected by choosing a better non-regular language:

$L= \mathscr{L}(a^*b^*)\cup \{a^nb^nc^n : n\geq0\}$ is non-regular.

$\endgroup$
  • $\begingroup$ Recipe: pick the non-regular partner so that the union is disjoint. Then the closure-properte proof always works. (Or does it?) $\endgroup$ – Raphael Feb 9 '16 at 8:25
  • $\begingroup$ Note that in the examples $\mathscr{L}(a^*)$ and $\{a^nb^n:n\geq 0\}$ aren't entirely disjoint. They share the word $\epsilon$. I would say that the languages have to be "sufficient disjoint" to make sure that the intersection will recover the known non-regular language. $\endgroup$ – Renato Sanhueza Feb 9 '16 at 17:53
  • 2
    $\begingroup$ The closure-property proof always works if the intersection of a non-regular language $N$ and its regular partner $R$ is regular (e.g. finite as in the two answers here or empty as @Raphael mentioned). Too see this one can use a "test" regular language $R_T = \overline{R} \cup (R \cap N)$ [this is where we want $R \cap N$ to be regular] and an equation $(R \cup N) \cap R_T = N$ to prove $(R \cup N)$ is regular. $\endgroup$ – Anton Trunov Feb 9 '16 at 19:51
  • $\begingroup$ @AntonTrunov nice catch! $\endgroup$ – Renato Sanhueza Feb 9 '16 at 21:19
2
$\begingroup$

Note that any non-regular language is infinite, since any finite language is regular.

Instead of searching for infinite regular subset in some given non-regular language, why don't we try to construct a non-regular language that contains an infinite regular language?

To do that we can take some context-free language, which is not regular, e.g. classical $a^nb^n, n \ge 0$, and "add" some infinite regular language to it. By "add" I mean the union operation on sets.

I should notice that one has to be careful while "adding" an infinite regular language to a non-regular one, since $L(a^nb^n) \cup \Sigma^* = \Sigma^*$, which is obviously regular.

So let's take a regular language $L(a^*)$, which has only one string in common (the empty string) with $L(a^nb^n), n \ge 0$ as our candidate "addition".

It's easy to prove the language $L(a^*) \cup L(a^nb^n), n \ge 0$ is non-regular (context-free). And its regular subset $L(a^*)$ is infinite.

$\endgroup$

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.