in Theory of Computation
244 views
0 votes
0 votes

in Theory of Computation
244 views

1 comment

The answer given in the test series says only c and d is correct. However, I think option b should be true as well. If I am wrong can anyone explain, please
0
0

1 Answer

1 vote
1 vote

Just relate it with proper subset concept of set theory

suppose, set A ={1,2,3,4}

Its proper subset is any subset of A that contains atleast 1 element less than A, that means A is not a proper subset of itself.

but as empty set (phi) $\Phi$ is a subset of A that has atleast 1 element less than A so it is also a proper subset of A.

infact in general the empty set (phi) is a proper subset of every set except for the empty set, and no set is a proper subset of itself.

 

Similarly, if String S= “abcd” then,

empty string epsilon($\epsilon$) is also one of its prefixes.

So its prefixes are $\epsilon$, a , ab, abc , abcd

but since option b talks about proper prefix, then abcd is not considered, because

“A proper prefix of a string is a prefix that is not equal to the string itself”.

hence proper prefixes are  $\epsilon$ , a , ab , abc

Thus for a ‘n’ length string, the number of proper prefixes = n.

edited by

2 Comments

Okay, Got it.
So basically,

  • proper subset/substring contains at least one element less than the given set/string.
  • trivial subset/substrings are the empty set and the set/string itself.

We should be careful between the two! 

1
1
yes!!
1
1

Related questions