0
$\begingroup$

I just have general questions about sets and determining if they are regular languages.

i) If A is regular, and A is a subset of B, then B must be regular.

ii) If B is regular, and A is a subset of B, then A must be regular.

iii) If A and AB are regular, than B must be regular

iv) If Ai is an infinite family of regular sets, than the union of all those sets is regular.

For the third one, I know that AB can only be regular if B is regular, because a regular set * a irregular one is not regular.

Lost for the other ones.

Improve this question
$\endgroup$
7
  • $\begingroup$ You are wrong about iii: consider for example $A = \emptyset$ or $A = \Sigma^*$. $\endgroup$
    – Yuval Filmus
    Oct 15, 2015 at 15:44
  • 2
    $\begingroup$ Welcome to CS.SE! 1. Please ask only one question per question. The site format does not work well with multiple questions. You can ask separate questions. 2. We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$
    – D.W. ♦
    Oct 15, 2015 at 17:11
  • $\begingroup$ We probably have a duplicate for every one of the four questions, too. $\endgroup$
    – Raphael ♦
    Oct 15, 2015 at 17:37
  • 1
    $\begingroup$ For iii, consider $A = a^*$, and $B = \{a^{n^2} \colon n \ge 0\}$, so $A = A B$ is regular, $B$ isn't. $\endgroup$
    – vonbrand
    Oct 15, 2015 at 18:57
  • $\begingroup$ For iv, consider the infinite family of finite (regular) sets $A_i = \{a^{i^2}\}$, the infinite union is $\{a^{n^2} \colon n \ge 0\}$ $\endgroup$
    – vonbrand
    Oct 15, 2015 at 18:59

1 Answer 1

Reset to default
3
$\begingroup$

Always think of boundary cases. In this case - the languages that contain every string or no string.

Also, let $N$ be some arbitrary non-regular language.

i) The language that contains no strings, which is regular, is a subset of $N$.

ii) $N$ is a subset of the language that contains all strings, which is regular.

iv) For every string $S_i$ in $N$, construct a set $L_i$ that contains only $S_i$. Note that all of these constructed sets are trivially regular. But the union of all of these (infinite number of) constructed sets is $N$, which is not regular.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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