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 a single-tape TM simulating a multitape TM M, then the time taken by M1 to simulate n moves is O(n³).
C. A pushdown automaton behaves like a Turing machine when it has one auxiliary memory.
D. L = {aⁿbⁿcⁿ : n ≥ 1} is not context-free but is context-sensitive.
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. D only
Explanation
D is true. B is false (the simulation takes O(n²)), and C is false (a PDA needs two stacks to match a TM). A is a known theorem, but since no option pairs A with D, the keyed answer is 'D only'.More Theory of Computation and Compilers questions
- Which phase of the compiler checks the grammar of the program?
- Consider the following statements: A. The set of Turing machine codes for TMs that accept all inputs that are palindromes (possibly along w…
- Which of the following parsers is the most powerful?
- Which of the following statements is correct?
- A compiler for a high-level language that runs on one machine and produces code for another machine is called a
- Shift-reduce conflicts are resolved by: