This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “PSPACE”.

1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:

a) PSPACE

b) NPSPACE

c) EXPSPACE

d) None of the mentioned

View Answer

Explanation: PSPACE is the problem class which contains all set of decision problems which can be solved using a turing machine taking polynomial amount of space.

2. PSPACE is strictly the super set of:

a) Regular language

b) Context free language

c) Context Sensitive Language

d) None of the mentioned

View Answer

Explanation: Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -complete problem.

3. Savitch theorem relates to which of the following:

a) PSPACE=NPSPACE

b) Alternating Turing Machine

c) Time complexity

d) None of the mentioned

View Answer

Explanation: Some important conclusions of Savitch theorem includes:

a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.

b) NL∈L2

4. The class PSPACE is closed under the following operations:

a) Union

b) Concatenation

c) Kleene

d) All of the mentioned

View Answer

Explanation: The closure property of PSPACE class includes :- Union, Concatenation and Kleene operation.

5. Correct the given order:

NL∈ P∈ NP∈ PH∈ PSPACE

a) NP∈ P∈ NL∈ PH∈ PSPACE

b) NL∈ PH∈ NP∈ P∈ PSPACE

c) NL∈ P∈ NP∈ PH∈ PSPACE

d) None of the mentioned

View Answer

Explanation: The given order is the only correct order and further PSPACE belongs to EXPTIME class and subsequently occurs EXPSPACE class.

6. NL ∈ PSPACE ∈ EXPSPACE

The given relation involves which of the following theorems?

a) Space hierarchy theorem

b) Savitch’s theorem

c) Both (a) and (b)

d) None of the mentioned

View Answer

Explanation: From space hierarchy theorem: NL ∈ NPSPACE, from Savitch’s theorem: NPSPACE= PSPACE.

7. Statement : All PSPACE problems can be reduced to PSPACE-complete problems.

State true or false:

a) true

b) false

View Answer

Explanation: PSPACE-complete problems are the most difficut problems is PSPACE. Finding a simple solution to PSPACE-complete means simple solution to all other problems in PSPACE because all PSPACE problems can be reduced to PSPACE-complete problems.

8. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.

a) time

b) space

c) both time and space

d) none of the mentioned

View Answer

Explanation: Though it may use extra time, but as PSPACE=NPSPACE from savitch’s theorem, we can say that space taken is same for both the machins, deterministic as well as non-deterministic.

9. Complement of all the problems in PSPACE is ________

a) PSPACE

b) NL

c) P

d) All of the mentioned

View Answer

Explanation: The complement of all the problems in PSPACE are also in PSPACE, meaning co-PSPACE= PSPACE.

10. Which of the following PSPACE can be characterized into?

a) APTIME

b) AP

c) Quantom complexity class

d) None of the mentioned

View Answer

Explanation: An alternative characterization of PSPACE is a set of problems decidable by a turing machine in polynomial time, sometimes called, APTIME or AP.

**Sanfoundry Global Education & Learning Series – Automata Theory.**

To practice all areas of Automata Theory, __here is complete set of 1000+ Multiple Choice Questions and Answers__.