McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) , Master of Computer Applications (MCA) .
Chapters
| 151. |
The set which is not countable if we have ∑ = {a, b}, is |
| A. | Set of all languages over ∑ accepted by turing machine |
| B. | Set of all regular languages over ∑ |
| C. | Set of all strings over ∑ |
| D. | Set of all languages over ∑ |
| Answer» D. Set of all languages over ∑ | |
| 152. |
How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times? |
| A. | n+1 |
| B. | n+2 |
| C. | n |
| D. | 2n |
| Answer» B. n+2 | |
| 153. |
Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is |
| A. | 10 |
| B. | 01 |
| C. | 101 |
| D. | 110 |
| Answer» A. 10 | |
| 154. |
The set that can be recognized by a deterministic finite state automaton is |
| A. | The set {1, 101, 11011, 1110111, …….} |
| B. | The set of binary string in which the number of 0’s is same as the number of1’s |
| C. | 1, 2, 4, 8……2n ….. written in binary |
| D. | 1, 2, 4, 8……2n ….. written in unary |
| Answer» C. 1, 2, 4, 8……2n ….. written in binary | |
| 155. |
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. | |
| 156. |
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 | |
| 157. |
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 | |
| 158. |
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 | |
| 159. |
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 | |
| 160. |
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 | |
| 161. |
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 | |
| 162. |
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 | |
| 163. |
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 | |
| 164. |
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 | |
| 165. |
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 | |
| 166. |
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) | |
| 167. |
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 | |
| 168. |
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 | |
| 169. |
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 | |
| 170. |
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. | |
| 171. |
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 Σ | |
| 172. |
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 | |
| 173. |
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 Studing? Take A Test.
Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.