edited by
5,701 views
19 votes
19 votes

Let $L \subseteq \{0,1\}^*$. Which of the following is true?

  1. If $L$ is regular, all subsets of $L$ are regular.
  2. If all proper subsets of $L$ are regular, then $L$ is regular.
  3. If all finite subsets of $L$ are regular, then $L$ is regular.
  4. If a proper subset of $L$ is not regular, then $L$ is not regular.
edited by

3 Answers

Best answer
32 votes
32 votes
  1. If L is regular, all subsets of L are regular.
    False.
    Counter Ex. $L = \{ a + b \}^*$ then its subset $\{ a^n \  b^n ; n > 0\}$ is not regular.
     
  2. If all proper subsets of L are regular, then L is regular.
    True.
    Proof: Take any proper subset of $L$ says $L_1$, $L_1$ is regular by definition.
    $L_2 = L - L_1$B 
    $L_2$ is also regular because it is also a proper subset of $L$.

    And we know that Union of two regular set is also regular.
    $L_1 \cup L_2 = L$. Hence $L$ is also regular.

    I have a strong feeling that L is finite that's why all its proper subsets are regular. 
     
  3. If all finite subsets of L are regular, then L is regular.
    False.
    Counter Ex: $L = \{ a^n \ b^n ; n > 0\}$, $L$ is not regular, it is context free.
    Now take any finite subset of $L$, this will be regular.
    Note: Take only, finite subset of L.
     
  4. If a proper subset of L is not regular, then L is not regular.
    False
    e.g., $L = \{a + b\}^*$ is regular, Its proper subset $\{ a^n \ b^n ; n > 0\}$ is not regular.

Correct Answer: $B$

edited by
11 votes
11 votes

Adding to the Answer provided by Hemant,


Option C : False

"If all finite subsets of $L$ are regular, then $L$ is regular."

Every finite language is (trivially) Regular. So, Every Finite subset of a language $L$ indeed always is Regular. So, This Hypothesis that "If all finite subsets of $L$ are regular" is Always True regardless of what $L$ is. $L $ could be any language, It could also be Non-regular. 


Option B : True

"If all proper subsets of $L$ are regular, then $L$ is regular."

This is True and we will see "Why", by taking a more general result which implies that "If all proper subsets of $L$ are regular then $L$ is Finite and Hence Regular."


Claim : "every infinite language $L$ has a non-regular subset"

Proof : 

Case 1 : If $L$ is Non-regular :

Then Since $L$ itself is a subset of $L$, we can say that the claim holds good. Moreover if we remove Finite number of strings from $L$, It will still remain Non-regular.

Case 2 : If $L$ is Regular :

Then $L$ will satisfy Pumping lemma for Regular languages which states that 

If $L$ is Regular then $\exists P \geq 1$, such that $\forall $ strings $w \in L,$ where $|w| \geq P$, $\exists x,y,z,$ such that $w = xyz$ and $|xy| \leq P$ and $|y| \geq 1$ and $\forall q \geq 0$, $xy^qz \in L$

So, Since $L$ is Regular and Infinite, let's pick any random string $w = xyz$ in $L$ such that $|w| \geq P$, then by pumping lemma, all strings of the form $xy^qz$ will be in $L$. So, Let's take a subset $S$ of $L$ which is

$S = \left \{ xy^qz| q\,\, is\,\, Prime \right \}$

Clearly this subset $S$ of $L$ is Not Regular.

Hence, Our Claim that  "Every Infinite language has a Non-regular subset" is True. 


 The above result implies the following :

 If all proper subsets of $L$ are regular, then $L$ is Finite and hence, Regular.

edited by
1 votes
1 votes

Ans C) Every finite subset should always be regular

A set may be regular

It's all subset is not regular all the time

Say (0+1)* is regular but 0n1n is not regular

Related questions

11 votes
11 votes
1 answer
1
go_editor asked May 23, 2016
957 views
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Cons...