2
$\begingroup$

I have been looking around for a good source to answer the following question. Have read a few different sources but have not found the answer I was looking for.

The question is:

Give an example of an infinite set of:

a. Regular languages whose union is a regular language

b. Regular languages whose union is a non-regular language

c. Non-regular languages whose union is a regular language

d. Non-regular languages whose union is a non-regular language

I've used this post to answer part b, and I understand the method behind it (at least I think I do).

What is the right way to approach this question?

Wouldn't an infinite set of anything constitute a non-regular language, by definition?

$\endgroup$
  • $\begingroup$ What would be a good resource for more information on this subject? $\endgroup$ – Immanuel May 31 at 14:53
1
$\begingroup$

a. is pretty easy. Just consider $\{a\}^\ast = \bigcup_{i \in \mathbb{N}_0} \{a\}^i$. This also answers the last question in your post (i.e., regular does not mean finite).

The answer to b., as you have said, can be found in the linked question.

Finally, for c. and d. you can use subsets of $\{ 0^n 1^n \mid n \in \mathbb{N}_0 \}$ and $\{ 1^n 0^n \mid n \in \mathbb{N}_0 \}$, which are both non-regular languages. Hint: The exercise text does not require the languages to be disjoint.

$\endgroup$
  • $\begingroup$ Regarding a. {a}^i is different than {a^i} correct? So what does {a}^i, I'm not sure I understand the notation. Would {a}^2 = {{a},{a}}? $\endgroup$ – Immanuel May 31 at 14:46
  • $\begingroup$ In this case, $\{ a \}^i = \{ a^i \}$. Nevertheless, $\{ a, b \}^2 = \{ aa, ab, ba, bb \}$. See here, for example. $\endgroup$ – dkaeae May 31 at 14:52
  • $\begingroup$ Much clearer! Thank you! $\endgroup$ – Immanuel May 31 at 14:55
1
$\begingroup$

Regarding a and b, let us make the following observation:

Every language is a union of regular languages.

This follows from the identity $$ L = \bigcup_{w \in L} \{w\}. $$

For part c, it is easy to write $\Sigma^*$ as a union of infinitely many distinct non-regular languages. Using your favorite non-regular language $L$, $$ \Sigma^* = \bigcup_{w \in \Sigma^*} (L \cup \{w\}). $$

For part d, again take your favorite non-regular language $L$. Then $$ L = \bigcup_{n=0}^\infty \{ w \in L : |w| \geq n \}. $$ Since $L$ is infinite, infinitely many of the summands would be distinct.

$\endgroup$
  • $\begingroup$ Regarding c. If L is a non-regular language, wouldn't a union of it to a word in Σ∗ still be considered non-regular? $\endgroup$ – Immanuel May 31 at 14:52
  • $\begingroup$ By "favorite non-regular language L" do you mean I could essentially use any non-regular language? Although I would probably just use the classic a^i b^i when i>=0. $\endgroup$ – Immanuel May 31 at 15:11
  • $\begingroup$ I don’t really understand your comment on part c. We are looking for a union of non-regular languages. $\endgroup$ – Yuval Filmus May 31 at 16:00
  • $\begingroup$ Could you give me an example for c. and d. I find it hard to visualize them. $\endgroup$ – Immanuel May 31 at 17:18
  • $\begingroup$ Use your favorite non-regular language $L$, and see for yourself what happens. $\endgroup$ – Yuval Filmus May 31 at 17:59

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.