MCQ Computer Science

Automata Theory Multiple Choice Question & Answers (MCQs) set-13

1. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned

View Answer

Answer: d
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation.
2. The space complexity of a turing machine is undefined if:
a) It is a multitape turing machine
b) If no string of length n causes T to use infinite number of tape squares
c) If some input of length n causes T to loop forever
d) None of the mentioned

View Answer

Answer: c
Explanation: If there exists an input string of length n that causes T to use an infinite number of tape squares, the space complexity of the turing machine is undefined.
3. Which of the following are probalistic algorithms?
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned

View Answer

Answer: d
Explanation: Monte Carlo algorithms are very vast, but only probably correct. On thr other side, Las Vegas algorithms are always correct, but probably fast.
4. Which of the following set of computable functions are decidable?
a) The class of computable functions that are constant, and its complement
b) The class of indices for computable functions that are total
c) The class of indices for recursively enumerable sets that are cofinite
d) All of the mentioned

View Answer

Answer: d
Explanation: According to Rice’s theorem, if there exists atleast one computable function in a particular class C of computable functions and another computable function not in C then the problem deciding whether a particular program computes a function in C is undecidable.
5. Which among the following are semi decidable?
a) Empty-DFA
b) Rec-NFA
c) Infinite-DFA
d) All of the mentioned

View Answer

Answer: d
Explanation: All are the properties of regular languages and all are decidable languages.
6. Which of the following are decidable problems?
a) Can a particular line of code in a program ever be executed?
b) Do two given CFG’s generate the same language
c) Is a given CFG ambiguous?
d) None of the mentioned

View Answer

Answer: d
Explanation: All of the mentioned problems are undecidable.
7. Which of the following can lack in a Universal computer?
a) Turing Complete Instruction set
b) Infinite memory
c) Infinite time
d) None of the mentioned

View Answer

Answer: d
Explanation: Real computers which are manufactured till date, all are similar to single taped turing machine. However, they have limited physical resources so they are linearly bounded complete on the contrary.
8. Which among the following options are correct?
Statement 1: TMs can accept languages that are not accepted by any PDA with one stack.
Statement 2: But PDA with two stacks can accept any language that a TM can accept.
a) Statement 1 and 2, both are correct
b) Statement 1 is correct but Statement 2 is false
c) Statement 2 is correct while Statement 1 is false
d) Statement 1 and 2, both are false

View Answer

Answer: a
Explanation: Both the statements are true. Both the statements are properties of Multistack machines.
9. Enumerator is a turing machine with __________
a) an output printer
b) 5 input tapes
c) a stack
d) none of the mentioned

View Answer

Answer: a
Explanation: Here, the turing machine can use the printer as an output device to print strings.
Note: There is no input to an enumerator. If it doesn’t halt, it may print an infinite set of strings.
10. Which of the following is/are a basic TM equivalent to?
a) Multitrack TM
b) Multitape TM
c) Non-deterministic TM
d) All of the mentioned

View Answer

Answer: d
Explanation: Tms can be used as both: language recognizers/Computers. TMs are like universal computing machines with universal storage.
11. Which of the following is true about Turing’s a-machine?
a) a stands for automatic
b) left ended, right end-infinite
c) finite number of tape symbols were allowed
d) all of the mentioned

View Answer

Answer: d
Explanation: Turings a- machine or automatic machine was left ended,right end infinite.Any of finite number of tape symbols were allowed and the 5 tuples were not in order.
12. If T1 and T2 are two turing machines. The composite can be represented using the expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned

View Answer

Answer: a
Explanation: If T1 and T2 are TMs, with disjoint sets of non halting states and transition function d1 and d2, respectively, we write T1T2 to denote this composite TM.
13. Which of the following statements are false?
a) Every recursive language is recursively ennumerable
b) Recursively ennumerable language may not be recursive
c) Recursive languages may not be recursively ennumerable
d) None of the mentioned

View Answer

Answer: c
Explanation: Every recursive language is recursively ennumerable but there exists recursively ennumerable languages that are not recursive. If L is accepted by a Non deterministic TM T, and every possible sequence of moves of T causes it to halt, then L is recursive.
14. State true or false:
Statement: RAM model allows random access to indexed memory locations.
a) true
b) false

View Answer

Answer: a
Explanation: In computer science, Random access machine is an abstract machine in the general class of register machines. Random access machine should not be confused with Random access memory.
15. Which of the following can be used to prove a language is not context free?
a) Ardens theorem
b) Power Construction method
c) Regular Closure
d) None of the mentioned

View Answer

Answer: c
Explanation: We can use the properties of regular closure to prove that a language is not a context free language. Example: Intersection of context free language and regular language is a context free language. Proof by contradiction helps here.

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Check Also
Close
Back to top button