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
View Answer

Answer: a
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
View Answer

Answer: c
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
View Answer

Answer: a
Explanation: Some important conclusions of Savitch theorem includes:
a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.
b) NL∈L2
advertisement
advertisement

4. The class PSPACE is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
d) All of the mentioned
View Answer

Answer: d
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

Answer: c
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
View Answer

Answer: c
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

Answer: a
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.
advertisement

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

Answer: b
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
View Answer

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

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

Answer: d
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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.