Solution

The correct answer is D only

Key Points

• A. A context free language is generated by LR(0) grammar if and only if it is accepted by a deterministic pushdown automata and has prefix property:
  • This statement is incorrect because a context-free language can be generated by an LR(0) grammar, but it does not need to be accepted by a deterministic pushdown automaton (DPDA).
  • Moreover, LR(0) grammars don't necessarily generate languages with the prefix property; they can produce languages where a prefix of a valid string is also a valid string, which is not always handled well by a DPDA.
• B. If M1 is the single tape TM simulating multilape TM M, then time taken by M1 to simulate n moves is (n³):
  • ​This statement is incorrect because the best known upper bound for simulating a multi-tape Turing machine M on a single-tape Turing machine M1 is quadratic, i.e., O(n²), not cubic.
• C. Push down automata behaves like a Turing machine when it has one auxiliary memory:
  • This statement is incorrect. While a PDA with two or more stacks does have the same computational power as a Turing machine, the concepts are distinct, and a multi-stack PDA should not directly be referred to as a Turing machine.ed so far, effectively simulating the 'unbounded' nature of a Turing machine's tape.
• D. L= L= {anbncn : n ≥ 1} is not context free but context sensitive:
  • This statement is correct. The language L= {anbncn : n ≥ 1} is a context-sensitive language, not a context-free language.
  • It cannot be represented by a context-free grammar (CFG) because it requires a mechanism to enforce that the number of a's, b's, and c's are equal, which is beyond the capabilities of a CFG.
  • However, it can be represented by a context-sensitive grammar which has the power to enforce such constraints.

So, only Statement D is correct. 

Mistake Points Official paper UGC don't give option D individual so UGC dropped the question.