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 : Click on Discuss to view users comments. |
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 : Click on Discuss to view users comments. |
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 : Click on Discuss to view users comments. |
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 : Click on Discuss to view users comments. |
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 G1 G2 and it is undecidable whether L (G1) = L (G2). |
| D. | Given two regular grammars G1 G2 and it is undecidable whether L (G1) = L (G2) |
|
Option: D Explanation : Click on Discuss to view users comments. |
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
