info@avatto.com
+91-9920808017
0. 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⌉)
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
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
