The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
904 views

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only.

Let $r=1(1+0)^*, s=11^*0 \text{ and } t=1^*0 $ be three regular expressions. Which one of the following is true?

  1. $L(s) \subseteq L(r)$ and $L(s) \subseteq L(t)$

  2. $L(r) \subseteq L(s)$ and $L(s) \subseteq L(t)$

  3. $L(s) \subseteq L(t)$ and $L(s) \subseteq L(r)$

  4. $L(t) \subseteq L(s)$ and $L(s) \subseteq L(r)$

  5. None of the above

 

asked in Theory of Computation by Veteran (68.8k points) | 904 views
L(r) = $1(1+0)^*$
L(s) = $1^+0$
L(t) = $1^*0$
(A) and (C) are answer!

3 Answers

+25 votes
Best answer
ans is A and C

to know the ans let us check all the options.

a) $L(s)\subseteq L(r)$:  strings generated by $s$ are any numbers of 1's followed by one 0, i.e., $10,110,1110,1110,\dots$. Strings generated by $r$ are is 1 followed by any combination of 0 or 1, i.e., $1,10,11,1110,101,110 \dots$. This shows that all the strings that can be generated by $s$, can also be generated by $r$ it means $L(s)\subseteq L(r)$ is true.
$L(s)\subseteq L(t)$: here strings generated by $t$ are any numbers of 1 (here 1* means we have strings as $\epsilon,1,11,111,\dots$) followed by only one 0, i.e., $0,10,110,1110, \dots$. So we can see that all the strings that are present in $s$ can also be generated by $t$, hence $L(s) \subseteq L(t)$ which shows that option A is true.

b) $L(r)\subseteq L(s)$: this is false because string 1 which can be generated by $r$, cannot be generated by $s$.

c) Same as option A.

d) $L(t) \subseteq L(s)$: this is false because string 0 which can be generated by $t$,cannot be generated by $s$.
answered by Loyal (4.4k points)
selected by
Both 's' and 't' looks same..
t can generate only zero while S cannot thus T is superset of S and not subet .Thus only c is correct.

 it should be strictly subset in the all cases above.

please correct if i am wrog? @ArjunSir
+2 votes
option A and C are the same and are the answers as well.
answered by Veteran (19.5k points)
+2 votes
If we take simpler strings,

t accepts 0, s doesn't. But both accept 10. So s is a subset of t.

r accepts 1, s doesn't. But both accept 10. So, s is a subset of r.

So, options A and C, as both are the same.
answered by (265 points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,330 questions
39,146 answers
108,244 comments
36,501 users