UGC NET CSE | December 2018 | Part 2 | Question: 31

Question

Let $r=a(a+b)^*, \: s=aa^*b$ and $t=a^*b$ be three regular expressions.

Consider the following :

1. $L(s) \subseteq L(r )\text{ and } L(s) \subseteq L(t)$
2. $L(r ) \subseteq L(s) \text{ and } L(s) \subseteq L(t)$

Choose the correct answer from the code given below :

• A. Only i is correct
• B. Only ii is correct
• C. Both i and ii are correct
• D. Neither i nor ii is correct

Answer 1

Given that,

S = a.a*.b and T = a*b

T = a*b = (∈ + a) (a*.b)

Compare S and T, you will get it as L(S) ⊆ L(T).

 

R = a (a+b)* ==> every string which have prefix by a,

Note that you can't compare T with R, why because, T may contain the strings which have not starts with a

∴ R ⊈ T and T ⊈ R

 

Coming to S, it is also contains the strings which are starts with a.

S = a. (a*b) where R = a. (a+b)* = a. (a*. b*)*

Compare S and T, you will get it as L(S) ⊆ L(R).

Answer 2

the correct anser is "L(s) is $ proper subset$  of L(r)" and  L(s) is  $proper subset$ of L(t) "

hence the answer is 2

edit: iam elaborating the answer and you people can take what is in it for you.

1. when we say "A ⊆ B" then we means set A can have some( may be 0 ) or all the elements of set B

2. when we say  "A proper subset of B" then this means that set A can have some not all the elements of A

3. language by L(r) is = all the strings that starts with " a " = {a, ab, aa, abb, aba, aab, aaa, ... }

4. language by L(s) = aa*b = a+ b = string with atleast one "a" followed by exactly one "b" = {ab, aab, aaab,.....}

5. language by L(t) = a*b = any number of "a " followed by exactly one "b" = {b, ab, aab, aaab,....}

6. clearly form 3 and 4 it can be said that  L(s) is proper subset of L(r) ( since elements are given so the  we can tell exactly whether they are  proper subset or not)

7.from 4 and 5 it can be exactly said that L(s) is proper subset of L(t) ( the elements are given so it can be said about it)

8. if its assumed that here the   " ⊆ " means same as " proper subset"  then the answer is 1, and if not the answer is 2. i will go with 2 since they are proper subset

Comments

@rakeshcoresoft look the answer must be  2. and if goes by your logic then the answer is 1. taker your call , as said  i have edited the above answer  look what you get in it and judge accrodingly, iam editing because you needed it urgently, hope that gives you prespective

 

---

@rakeshcoresoft, answer 2 only is correct as you can see in question r= {generates strings starting with a and any combination of a's and b's} , s={generates string starting a then any combination of a's and with b} and t ={any number of a's then end with b} 

but if you will say l(s) is subset of l(r) then it means l(s) generates full set of l(r) but it's not true right?

 but definition of proper set is "If A and B are two sets, then A is called the proper subset of B if A ⊆ B i.e., A ≠ B. The symbol ‘⊂’ is used to denote proper subset."

 So correct answer will be neither 1 nor 2.

---

What is the definition of Subset?

If A⊂B is true, then A⊆B is definitely true.

Answer 3

Option 2. is right

Regular language are not closed under subset and superset

https://courses.engr.illinois.edu/cs373/sp2009/Handouts/closure/regular-closure.html