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.

$\endgroup$
  • $\begingroup$ You are wrong about iii: consider for example $A = \emptyset$ or $A = \Sigma^*$. $\endgroup$ – Yuval Filmus Oct 15 '15 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 '15 at 17:11
  • $\begingroup$ We probably have a duplicate for every one of the four questions, too. $\endgroup$ – Raphael Oct 15 '15 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 '15 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 '15 at 18:59
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.

$\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.