TOC Test Series

Question

Consider the languages

(I) L1= {w#x , where w,x ∈ (0+1)* and # is a special character and w is a prefix of x } .
(II) L2={w#x , where w,x ∈ (0+1)* and # is a special character and w^R, is a prefix of x}.
(III) L3={w#x , where w,x ∈ (0+1)* and # is a special character and w^R, is a substring of x}
(IV) L4={w#x , where w,x ∈ (0+1)* and # is a special character and w^R, is suffix of x}

1.  (I) is recursive and (II), (III) and (IV) are DCFL.
2.   (I) is CFL but not DCFL , (II) and (III) is DCFL, (IV) is recursive but not CFL.
3.   (II) and (III) is DCFL (I) and (IV) is recursive but not CFL.
4.   (I) is recursive , (II) is DCFL , (III) and (IV) are CFL but not DCFL

Answer 1

Let us analyse one by one : 

i) For L1 , if w needs to be the prefix of x , then this is similar to : w # w p where p is the part other than the prefix which is 'w' in this case for the string part 'x' . So now this is nothing but comparision of w with w as we have # in between and # is a single symbol only so comparision of w with w is needed . And we know this is not achievable using single stack . Hence L1 is not a CFL but a CSL and hence recursive .

ii) For L2 , most of the thing is same except the fact that now we will have : w # w^R p .Hence now it is possible to implement with a single and that too with determinism i.e. we know when to push or pop as well how much to push or pop from the stack . The contents of 'w' are pushed to stack and when '#' comes we do just state transition as an indication that from next input symbol onwards which belongs to 'w^R' , the contents of 'w' will be popped as well . And the 'p' part can be anything(regular part) , hence need not to be worried . Hence L2 is DCFL .

iv) For L4 , we will have string of the form :  w # p w^R  . Now again since '#' is a symbol only , hence we have to take care of the 'w' as well as 'w^R' and hence we cannot ignore them here as well by substituting epsilon in place of 'w' and 'w^R' which would be a wrong substitution here . So we need to see the content of w as well as w^R . Now the thing is we do not know when the 'p' part would end and 'w^R' part would start so that we can pop the contents of w which is in stack currently . Hence it has non deterministic behaviour . Hence L4 is CFL but not DCFL . 

iii) For L3 , we need to check whether w^R is substring of 'x' in the similar manner like we checked for prefix and suffix in earlier cases . Here we will have string of the form : w # p w^R q  as w^R can be anywhere in middle in the 'x' part or can be its suffix or prefix . Now this problem becomes similar to L3 as we do not know when 'p' would end and w^R part would come .Hence L3 is a CFL but not DCFL.

Hence D) should be the correct option .

Comments

w is a prefix of x
say x is 0011
then w is epsilon,0,00,001,0011

Does it is correct and if so does your explanation is holding true?

sorry i am not getting it and rest i am still reading whole answer.

Can you please give example for each language,please, that will be very helpful and i  can draw some pda or can do some analysis.

Thanks :)

---

Ya its fine as per my understanding @sunil sarode ..:)

---

@arjun sir ,Can you please give example for each language,please, that will be very helpful and i  can draw some pda or can do some analysis.

---

https://gateoverflow.in/52134/which-of-following-features-cannot-be-captured-by-cfg 

It is example of L1