835 views

1 Answer

Best answer
3 3 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.

 

 

 

• selected by
Position:
Show:

Related questions

0 0 votes
0 0 answers
498
498 views
Dknights asked Jan 16, 2025
498 views
Can someone help in the below language is this regular, how to prove it @Deepak Poonia sir @Shaik Masthan sirNumber of 0s and 1s are equal and in each prefix of w number ...
1 1 vote
0 0 answers
289
289 views
pinklotus02 asked Dec 25, 2024
289 views
I am trying to classify languages into RL, DCFL, CFL, REL.Please correct me if I am wrong.Input Alphabets = {a,b}1. L = { wcw^r | w belongs to kleen closure} DCFL2. L...
0 0 votes
1 1 answer
206
206 views
Dknights asked Nov 15, 2024
206 views
Start symbol generating ε. (e.g.; S- ε)and also written Any Context-free Grammar without ε in its language has an equivalent CNF.source - https://www.geeksforgeeks.org/co...
0 0 votes
1 1 answer
335
335 views
Dknights asked Jan 8, 2024
335 views
a^n ww^r a^n .. (n>=0, w belongs to (a,b)*)Can someone please explain the flow how we will process the language in CFL.