1.From the options given below, the pair having different expressive power is
Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA) Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA) Single tape turning machine and multi tape turning machine Deterministic single tape turning machine and Non-Deterministic single tape turning machine
2.The problem that is undecidable -
Finiteness problem for FSA’s Membership problem for CFG’s Equivalence problem for FSA’s Ambiguity problem for CFG’s
3.The language which is generated by the grammar S-> aSa I bSb I a I b over the alphabet {a, b} is the set of
Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes
4.Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that
π is NP-complete π is NP-hard but not NP-complete π is in NP but not NP-complete π is neither NP-hard nor in NP
5.Out of the three problems S, Q and R, S is an NP-complete problem and Q and R are the two other problems not known to be in NP. Which one of the following statements is true if Q is polynomial time reducible to S and S is the polynomial time reducible to R?
Q is NP-complete R is NP-complete Q is NP-hard R is NP-hard
Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA) Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA) Single tape turning machine and multi tape turning machine Deterministic single tape turning machine and Non-Deterministic single tape turning machine
2.The problem that is undecidable -
Finiteness problem for FSA’s Membership problem for CFG’s Equivalence problem for FSA’s Ambiguity problem for CFG’s
3.The language which is generated by the grammar S-> aSa I bSb I a I b over the alphabet {a, b} is the set of
Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes
4.Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that
π is NP-complete π is NP-hard but not NP-complete π is in NP but not NP-complete π is neither NP-hard nor in NP
5.Out of the three problems S, Q and R, S is an NP-complete problem and Q and R are the two other problems not known to be in NP. Which one of the following statements is true if Q is polynomial time reducible to S and S is the polynomial time reducible to R?
Q is NP-complete R is NP-complete Q is NP-hard R is NP-hard
No comments:
Post a Comment