Bihar STET – TOC Practice Test | Set 1 ⋆ CSE Study247

Bihar STET – TOC Practice Test | Set 1

Questions 91-95 of 100

0% completed (0/100 answered)

Question 91

MCQ · Single Correct 1 mark

Previous Year Question Bihar STET C.S. 12.09.2023 (Shift-II) PYQ

Which level of the Chomsky Hierarchy represents 'Recursively Enumerable / Unrestricted Grammars'?

A Type 1 B Type 3 C Type 0 D Type 2

Question 92

MCQ · Single Correct 1 mark

What proper inclusion relationship holds across the four Chomsky Hierarchy language classes?

A Regular (Type 3) ⊂ Context-Free (Type 2) ⊂ Context-Sensitive (Type 1) ⊂ Recursively Enumerable (Type 0) B Type 2 ⊂ Type 3 ⊂ Type 0 ⊂ Type 1 C Type 1 ⊂ Type 0 ⊂ Type 3 ⊂ Type 2 D Type 0 ⊂ Type 1 ⊂ Type 2 ⊂ Type 3

Question 93

MCQ · Single Correct 1 mark

In complexity theory, what does the complexity class 'P' represent?

A Problems requiring Exponential time B Problems solvable in O(1) C Set of decision problems solvable by a Deterministic Turing Machine in Polynomial Time O($n^k)$ D Undecidable problems

Question 94

MCQ · Single Correct 1 mark

In complexity theory, what does the complexity class 'NP' represent?

A Not Solvable problems B Non-Polynomial time problems C Parallel time problems D Set of decision problems verifiable by a Deterministic TM in Polynomial Time (or solvable by a Nondeterministic TM in Polynomial Time)

Question 95

MCQ · Single Correct 1 mark

What is an 'NP-Complete' decision problem?

A A problem in P B An undecidable problem C A problem that belongs to NP and to which EVERY problem in NP can be reduced in Polynomial Time D A problem solved in O(n)