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.
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation.
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.
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.
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.
Explanation: Monte Carlo algorithms are very vast, but only probably correct. On thr other side, Las Vegas algorithms are always correct, but probably fast.
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.
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.
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.
Explanation: All are the properties of regular languages and all are decidable languages.
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.
Explanation: All of the mentioned problems are undecidable.
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.
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.
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.
Explanation: Both the statements are true. Both the statements are properties of Multistack machines.
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.
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.
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.
Explanation: Tms can be used as both: language recognizers/Computers. TMs are like universal computing machines with universal storage.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
