1. The decision problem is the function from string to ______________
a) char
b) int
c) boolean
d) none of the mentioned
View Answer
Explanation: The decision problem requires checking of input (string) has some property or not. That is a string to boolean transaction.
2. Diagonalization can be useful in:
a) To find a non recursively ennumerable language
b) To prove undecidablility of haltig problem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: Diagonalization is a technique we use for the following operations:
a) To find a non recursively ennumerable language.
b) To prove undecidablility of halting problem.
a) the input tape contents
b) position of the input head
c) distance of storage heads from symbol Z
d) all of the mentioned
View Answer
Explanation: Instantaneous description of a counter machine can be described by the state, the input tape contents, the position of input head, and the distance of storage heads from the symbol Z. The counter machine can really store a count on each tape and tell if the count is zero.
a) Every multitape turing machine has its equivalent single tape turing machine
b) Every multitape turing machine is an abstract machine
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: A multitape turing machine is an ordinary turing machine which is always abstract.And they do have their equivalent single tape turing machines.
Statement 2: Gamma is Cartesian product of a finite number of finite sets.
Which among the following is the correct option?
a) Statement 1 is the assertion and Statement 2 is the reason
b) Statement 1 is the reason and Statement 2 is the assertion
c) Statement 1 and Statement 2 are independent from each other
d) None of the mentioned
View Answer
Explanation: Cartesian product works like a struct in C/C++. For Example: Computer tape storage is something like 8 or 9 bits in each cell. One can recognize a multi track tape machine by looking at the transitions because each will have tuples as the read and write symbols.
Statement: If a language L is recursive, it is closed under the following operations:
a) Union
b) Intersection
c) Complement
d) All of the mentioned
View Answer
Explanation: The closure property of recursive languages include union, intersection and complement operations.
7. Which of the following are the models equivalent to Turing machine?
a) Multi tape turing machine
b) Multi track turing machine
c) Register machine
d) All of the mentioned
View Answer
Explanation: Many machines that might be thought to have more computational capability than a simple UTM can be shown to have no more power. They might compute faster or use less memory but cannot compute more powerfully i.e. more mathematical questions.
9. Which of the following steps are wrong with respect to infiniteness problem?
a) Remove useless variables
b) Remove unit and epsilon production
c) Create dependency graph for variables
d) If there is a loop in the dependency graph the the language is finite else infinite
View Answer
Explanation: If we are able to detect a loop in the formed dependency graph, then the language in infinite.
10. Which of the following does not obey pumping lemma for context free languages ?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned
View Answer
Explanation: Finite languages (which are regular hence context free ) obey pumping lemma where as unrestricted languages like recursive languages do not obey pumping lemma for context free languages.
11. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in ___________.
a) restricted form
b) parsed form
c) normal form
d) all of the mentioned
View Answer
Explanation: When the production in G satisfy certain restrictions, then G is said to be in ‘normal form’.
S->AB
A->a
a) S
b) A
c) B
d) None of the mentioned
View Answer
Explanation: Any variable A for which there is a production A-> x with x ? S* is called live.
S->aS| AB
A-> e
B-> e
D-> b
Reduce the grammar, removing all the e productions:
a) S->aS| AB| A| B, D-> b
b) S->aS| AB| A| B| a, D-> b
c) S->aS| AB| A| B
d) None of the mentioned
View Answer
Explanation: We will replace all the nullables wherever they appear in the right hand side of any production. D will not be erased as we are just removing nullable variables not completely simplifying the grammar.
a) empty variable
b) nullable
c) terminal
d) all of the mentioned
View Answer
Explanation: Any variable A for which the derivation: A->*e is possible is called Nullable.
a) e ? L(G)
b) w ? L(G)
c) e ? L(G)
d) w ? L(G)
View Answer
Explanation: Theorem: Let G = (V, T, S, P) be a CFG such that e ? L(G). Then there exists an equivalent grammar G’ having no e-productions.
