Unacademy Test

Question

Consider the language given below:

L={P!=w | P is prefix of w and w <-{0,1}*}

Which is TRUE about L?

A.L is CFL

B.L is DCFL

C.L is CSL    CORRECT ANSWER

D.L is regular

Answer 1

It’s not regular we can not write regular expressions for it.

Stack logic we can not use because if we push all the characters of ‘p’ then we can not compare the first character of p with the first character of ‘w’  as the first character of p will be at the bottom of the stack.

So, it’s not a Context Free Language.

L is Context-Sensitive Language.

If you can write a program to solve this problem(to accept this language) then it's Context-Sensitive Language as long as the space complexity is linear.

Now we can easily write a program to do this.

Code Hint:

Start comparing w and p from the beginning and if till the last character of p all the character matches then the string belongs to your language.

Comments

That’s true. But are other options False?

---

Yes, sir. Edited my answer.

It’s not regular we can not write regular expressions for it.

Stack logic we can not use because if we push all the characters of ‘p’ then we can not compare the first character of p with the first character of ‘w’  as the first character of p will be at the bottom of the stack.

So, it’s not CFL.