McqMate
Chapters
| 1. |
What is the reason behind a Turing machine is more powerful than finite state machine FSM? |
| A. | turing machine head movement is continued to one direction. |
| B. | turing machine head moment is in both directions i.e. left moment and right moment as well. |
| C. | turing machine has capability remember arbitrary long sequence of input string. |
| D. | all are correct. |
| Answer» C. turing machine has capability remember arbitrary long sequence of input string. | |
| 2. |
A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory. |
| A. | 0 |
| B. | exectly 2 |
| C. | 2 or more |
| D. | both exectly 2 or more are correct |
| Answer» C. 2 or more | |
| 3. |
The language L = {anbnan n≥ 1} is recognized by |
| A. | turing machine |
| B. | 2 pushdown automata |
| C. | post machine |
| D. | all are correct |
| Answer» D. all are correct | |
| 4. |
If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be |
| A. | recursive enumerable |
| B. | recursive |
| C. | context free language (cfl) |
| D. | none of them |
| Answer» A. recursive enumerable | |
| 5. |
If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be |
| A. | recursive enumerable |
| B. | recursive |
| C. | context free language |
| D. | none of these |
| Answer» C. context free language | |
| 6. |
Universal Turing machine (UTM) influenced the concepts of |
| A. | computability |
| B. | interpretive implementation of programming language |
| C. | program and data is in same memory |
| D. | all are correct |
| Answer» D. all are correct | |
| 7. |
The number of symbols necessary to simulate a Turing machine with m symbols and n states |
| A. | 4m × n + m |
| B. | 4m × n + n |
| C. | m+n |
| D. | none of them |
| Answer» A. 4m × n + m | |
| 8. |
A universal Turing machine is a |
| A. | reprogrammable truing machine |
| B. | two-tape turing machine |
| C. | single tape turing machine |
| D. | none of them |
| Answer» A. reprogrammable truing machine | |
| 9. |
He difference between a read-only Turing machine and a two-way finite state machine is |
| A. | head movement |
| B. | finite control |
| C. | storage capacity |
| D. | power |
| Answer» C. storage capacity | |
| 10. |
Which is correct regard an off-line Truing machine? |
| A. | an offline turing machine is a special type of multi-tape turing machine |
| B. | an offline turing machine is a kind of multi-tracks truing machine |
| C. | an offline turing machine is a kind of single-track turing machine |
| D. | none of them |
| Answer» A. an offline turing machine is a special type of multi-tape turing machine | |
| 11. |
Which of the following statement is wrong? |
| A. | power of ntm and tm is same |
| B. | for n ≥ 2, npda has some power as a tm |
| C. | for n ≥ 2, npda and 2pda have same power |
| D. | power of ntm and tm is not same |
| Answer» D. power of ntm and tm is not same | |
| 12. |
Four pairs are following; in each pair both objects have some common thing. Choose the odd pair; |
| A. | (tm, 2pda) |
| B. | (computer, utm) |
| C. | (2pda, npda) |
| D. | (fa, pda) |
| Answer» D. (fa, pda) | |
| 13. |
We think of a Turing machine’s transition function as a |
| A. | computer system |
| B. | software |
| C. | hardware |
| D. | all of them |
| Answer» B. software | |
| 14. |
Church’s Thesis supports |
| A. | a turing machine as a general-purpose computer system |
| B. | a turing machine an algorithm and an algorithm as a turing machine |
| C. | both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct |
| D. | none of them is correct |
| Answer» C. both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct | |
| 15. |
A random access machine (RAM) and truing machine are different in |
| A. | power |
| B. | accessing |
| C. | storage |
| D. | both accessing and storage are correct |
| Answer» D. both accessing and storage are correct | |
| 16. |
Choose the correct statement |
| A. | recursive set ⊆ recursive enumerable set |
| B. | total function is same as partial function |
| C. | recursive sets are analogous to total functions |
| D. | both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct. |
| Answer» D. both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct. | |
| 17. |
Given S = {a, b}, which one of the following sets is not countable? |
| A. | the set all strings over Σ |
| B. | the set of all language over Σ |
| C. | the set of all binary strings |
| D. | the set of all languages over Σ accepted by turing machines |
| Answer» B. the set of all language over Σ | |
| 18. |
In which of the stated below is the following statement true? “For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.” |
| A. | m1 is a non-deterministic finite automata |
| B. | m1 is a non-deterministic push-down automata |
| C. | m1 is a non-deterministic turing machine |
| D. | for no machine m1 use the above statement true |
| Answer» C. m1 is a non-deterministic turing machine | |
| 19. |
Which of the following conversion is not possible (algorithmically)? |
| A. | regular grammar to context-free grammar |
| B. | non-deterministic finite state automata to deterministic finite state automata |
| C. | non-deterministic pushdown automata to deterministic pushdown automata |
| D. | none deterministic turing machine to deterministic turing machine |
| Answer» B. non-deterministic finite state automata to deterministic finite state automata | |
Done Reading?