Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Consider following statements:
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.
B. If M1 is the single tape TM simulating multitape TM M, then time taken by M1 to simulate n moves is $(n^3)$.
C. Push down automata behaves like a Turing machine when it has one auxiliary memory.
D. $L={a^n b^n c^n : n \ge 1}$ is not context free but context sensitive.
Choose the correct answer from the options given below:
Solution
A is incorrect because LR(0) is a restricted class and the statement is not generally true.
B is incorrect because a single-tape TM can simulate a multitape TM with quadratic overhead, not cubic.
C is incorrect because a pushdown automata with one stack is not equivalent to a Turing machine.
D is correct because $L={a^n b^n c^n : n \ge 1}$ is not context free, but it is context sensitive.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
