Consider the following statements: A. A context-free language is generated by…

2023

Consider the following statements:

A. A context-free language is generated by an LR(0) grammar if and only if it is accepted by a deterministic pushdown automaton and has the prefix property.

B. If M1 is the single-tape Turing Machine simulating a multi-Tape TM M, then the time taken by M1​ to simulate n moves is (n3).

C. Pushdown automata behaves like a Turing machine when it has one auxiliary memory.

D. L={anbncn:n≥1} is not context-free but context-sensitive.

Choose the correct answer from the options given below:

  1. A.

    A, B and C only

  2. B.

    A, B only

  3. C.

    C, D only

  4. D.

    B, C only

Attempted by 9 students.

Show answer & explanation

Correct answer: C

Statement A is correct: A context-free language is generated by an LR(0) grammar if and only if it is accepted by a deterministic pushdown automaton (DPDA) and has the prefix property. Statement B is incorrect: The time taken by a single-tape TM to simulate n moves of a multi-tape TM is O(n^2), not O(n^3). Statement C is incorrect: A PDA has a stack (LIFO memory) while a TM has an infinite tape; they are not equivalent. Statement D is correct: The language L={a^n b^n c^n} cannot be generated by a context-free grammar (proven via Pumping Lemma) but is recognized by a Linear Bounded Automaton, making it context-sensitive. Therefore, statements A and D are correct.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Mppsc Assistant Professor