1,420 views
2 votes
2 votes
L = {B(N)#B(N+1) : B(N) represents binary pattern for given N. Example B(5)=101, N>=1}. Then which of the following is true for L?

(A). L is regular

(B). L is CFL but not regular

(C). L is Recursive but not CFL

(D). L is recursive enumerable but not recursive

1 Answer

Best answer
4 votes
4 votes

First of all some sort of comparision is required .So it is not regular at all..

But the additional constraint is the computing overhead as we can infinitely large value of n so we cannot compare n and n+1 using a stack simply .First computation of N+1 needs to be done and then comparision with input tape after reading '#'..

So due to this computational overhead , PDA cannot handle this .So this has to be done by a Turing Machine..A halting turing machine can be employed to find N+1..

Hence the given language should be recursive but not CFL..

Hence C) should be the correct option..

selected by
Answer:

Related questions

0 votes
0 votes
1 answer
3
Anmol Verma asked Dec 1, 2016
1,819 views
Construct right-linear grammar and left-linear grammar for the languageL ={anbm : n$\geq$2 , m$\geq$3}Explanation about this....???