Theory Of Computation MCQ - Recursively enumerable sets and Turning machines

1:

Which of the following is complement of a?

 A. Recursive language is recursive B. Recursively enumerable language is recursively enumerable C. Recursive language is either recursive or recursively enumerable D. None of these Answer Report Discuss Option: C Explanation : Click on Discuss to view users comments. Write your comments here:
2:

If nL can be recognized by a multitape TM with time complexity f, then L can be recognized by a one-tape machine with time complexity  DSD

 A. O( f 2) B. o( f 2) C. o(h) D. O(h2) Answer Report Discuss Option: A Explanation : Click on Discuss to view users comments. Suindu De said: (4:57am on Saturday 20th January 2018) n is a multiplier to that language so if f is the compleexity then f should nbe the complexity. Write your comments here:
3:

If T is a TM recognizing L, and T reads every symbol in the input string, τT(n) ≥  2n + 2, then any language that can be accepted by a TM T with τT(n) = 2n + 2 is

 A. regular B. not regular C. uncertain D. none of these Answer Report Discuss Option: C Explanation : Click on Discuss to view users comments. Write your comments here:
4:

Consider an alternate Turing machine model, in which there is an input tape on which the tape head can move in both directions but cannot write, and one or more work tapes, one of which serves as an output tape. For a function f, denoted by DSpace ( f ) , the set of languages that can be recognized by a Turning machine of this type which uses no more than f(n) squares on any work tape for any input string of length n. The only restriction we need to make on f is that f(n) > 0 for every n. The language of balanced strings of parentheses are in

 A. DSpace (1+  ⌈log2 (n + 1 ⌉). (⌈ x  ⌉) means the smallest integer greater than or equal to x. B. DSpace (1+ ⌈log2 n⌉) C. DSpace ( 1+ ⌈ log2 n2⌉) D. none of these Answer Report Discuss Option: A Explanation : Click on Discuss to view users comments. Write your comments here:
5:

Which of the following problems is solvable ?

 A. Writing a universal Turing machine B. Determining of an arbitrary turing machine is an universal turing machine C. Determining of a universal turing machine can be written for fewer than k instructions for some k D. Determining of a universal turing machine and some input will halt Answer Report Discuss Option: A Explanation : Click on Discuss to view users comments. Write your comments here:

Suggest an improvement

Syllabus covered in this section is-

• Regular languages and finite automata
• Context free languages and Push-down automata
• Recursively enumerable sets and Turing machines
• Undecidability, NPcompleteness
• Models of computation-Finite Automata
• Pushdown Automata
• Non-detenninism and NFA. DPDA and PDAs and Languages accepted by these Structures
• Grammars, Languages,
• Non- computability and Examples of non-computable problems

This Section covers Theory of Computation Questions Answers .These questions can be used for the preparation of various competitive and academic exams like

• UGC NET Computer Science
• Pre PhD Entrance Exam
• DOEACC Exams
• Kendriya Vidyalaya Sangathan Entrance Exam
• GATE Computer Science
• Post Graduate Computer Science Test
•  PhD Entrance Exam
• Computer Engineering
• National Eligibility Test (NET)
• State Eligibility Test (SET)

Who can benefit

• Theory of Computation Objective Questions Answers can be used by any student who is preparing for PhD entrance exam, pre PhD entrance exam, entrance exam or any other such exam.
• Any student who is preparing for DOEACC exams can also use Theory of Computation questions answers for preparation of his exams.
• Automata Theory mcq can be useful for the students who are pursuing any undergraduate or post graduate degree in computer science like BE, ME , Btech, Mtech, .BSc, MSc, BCA, MCA, BS, MS  or any other such degree
• Theory of Computation mcq with answers and explanation can also be useful for the students who are preparing for any competitive exam or recruitment exams like GATE Computer Science, UGC NET Computer Science, Kendriya Vidyalaya Sangathan PGT exam, PSU, IES or any other such exam.
• Theory of Computation multiple choice questions answers can also be used by any candidate who wants to gain credits in Theory of Computation in BS Computer science or MS Computer science.
• Theory of Computation mcq questions answers can be used for the preparation of National Eligibility Test (NET) and State Eligibility Test (SET).
• You can download Theory of Computation mcq pdf from this site.

Various Search Terms Used For This Section Are