Automata Theory Questions and Answers – PSPACE

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

Explanation: PSPACE is the problem class that 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

Explanation: Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary deterministic 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

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

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

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) Space hierarchy and Savitch’s theorems
d) None of the mentioned

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

Explanation: PSPACE-complete problems are the most difficult 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

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 machines, 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

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

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]