Which of the following is not primitive recursive but partially recursive ?
A. | Carnot's function |
B. | Ricmann function |
C. | Bounded function |
D. | Ackermann's function |
Option: D Explanation : |
Turing machine (TM) is more powerful than FMS (Finite State Machine) because
A. | tape movement is confined to one direction |
B. | it has no finite state |
C. | it has the capability to remember arbitrarily long sequences of input symbols |
D. | none of these |
Option: C Explanation : |
If f : N--> N. If L can be recoognized by a TM T, so that τ_{T}(n) ≤ f (n) for all but finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).
A. | L ∈Time (f) |
B. | L ∈ Time(cf) |
C. | L ∈ Time (h) |
D. | none of these |
Option: A Explanation : |
Let s is a step-counting function satisfying s(n) ≥ n, and L be a language accepted by a (multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes for an input string of length n, then T ∈
A. | Space(s) |
B. | F(n) |
C. | Time(f) |
D. | Time(h) |
Option: A Explanation : |
Which of the following statements is false ?
A. | Halting problem of Turing machines is undecidable |
B. | Determining whether a context-free grammar is ambiguous is undecidable |
C. | Given two arbitrary context-free grammars G_{1} G_{2} and it is undecidable whether L (G_{1}) = L (G_{2}). |
D. | Given two regular grammars G_{1} G_{2} and it is undecidable whether L (G_{1}) = L (G_{2}) |
Option: D Explanation : |
Syllabus covered in this section is-
This Section covers Theory of Computation Questions Answers .These questions can be used for the preparation of various competitive and academic exams like
Who can benefit
Various Search Terms Used For This Section Are