info@avatto.com
+91-9920808017
1. Which of the following is complement of a?
Recursive language is recursive
Recursively enumerable language is recursively enumerable
Recursive language is either recursive or recursively enumerable
None of these
Your email address will not be published. Required fields are marked *
Report
Name
Email
Website
Save my name, email, and website in this browser for the next time I comment.
Comment
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
O(f2)
o(f2)
o(h)
O(h2)
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
regular
not regular
uncertain
none of these
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
DSpace (1+  ⌈log2 (n + 1 ⌉). (⌈ x  ⌉) means the smallest integer greater than or equal to x.
DSpace (1+ ⌈log2 n⌉)
DSpace ( 1+ ⌈ log2 n2⌉)
5. Which of the following problems is solvable?
Writing a universal Turing machine
Determining of an arbitrary turing machine is an universal turing machine
Determining of a universal turing machine can be written for fewer than k instructions for some k
Determining of a universal turing machine and some input will halt
Login with Facebook
Login with Google
Forgot your password?
Lost your password? Please enter your email address. You will receive mail with link to set new password.
Back to login
