Register

CMI2012-A-01

• edited by
10,354 views
20 20 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.

3 Answers

Best answer
33 33 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
13 13 votes

MUST WATCH: https://youtu.be/Z4W7Qi0wr-c?feature=shared

Option C : False

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

Every finite language is Regular. So, Every Finite subset of any 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.

MUST WATCH: https://youtu.be/Z4W7Qi0wr-c?feature=shared

Countability Complete Playlist: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared

• edited by
1 1 vote

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

Voting & Accepting an answer helps improve the community
Answer:
← Previous · Is there any differe...Next → · CMI2012-A-02
← Previous in category · produtionNext in category → · CMI2012-B-02a
Position:
Show:

Related questions

11 11 votes
1 1 answer
1.4k
1.4k views
go_editor asked May 23, 2016
1,356 views
CMI2012-B-01
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...
4 4 votes
1 answers 1 answer
2.0k
2.0k views
go_editor asked May 27, 2016
2,024 views
CMI2012-B-02b
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$.Construct a finit...
15 15 votes
1 answers 1 answer
3.2k
3.2k views
go_editor asked May 23, 2016
3,162 views
CMI2012-B-02a
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$.Construct a finit...
16 16 votes
2 answers 2 answers
2.2k
2.2k views
go_editor asked May 22, 2016
2,191 views
CMI2012-A-10
Consider the following functions $f$ and $g$. f(){ x = x-50; y = y+50; }g( ) { a = a+x; a = a+y; }Suppose we start with initial values of $100$ for $x, 200$ for $y$, and ...