Question 31Asked in Bihar STET 2025 Paper II Computer Science, 4 Nov 2025, Shift 2 (2:00 PM) + 1 more paper

Which of the following conversion is not possible (algorithmically)?निम्नलिखित में से कौन सा रूपांतरण संभव नहीं है (एल्गोरिथ्मिक रूप से)?

निम्नलिखित में से कौन सा रूपांतरण संभव नहीं है (एल्गोरिथ्मिक रूप से)?
  1. ARegular grammar to context-free grammarनियमित व्याकरण से संदर्भ-मुक्त व्याकरण तक
  2. BNon-deterministic pushdown automata to deterministic pushdown automataगैर-नियतात्मक पुशडाउन ऑटोमेटा से नियतात्मक पुशडाउन ऑटोमेटा
  3. CNon-deterministic finite state automata to deterministic finite state automataगैर-नियतात्मक परिमित अवस्था ऑटोमेटा से नियतात्मक परिमित अवस्था ऑटोमेटा
  4. DNon deterministic Turing machine to deterministic Turing machineगैर नियतात्मक ट्यूरिंग मशीन से नियतात्मक ट्यूरिंग मशीन
Show answerHide answer

Correct answer: (B) Non-deterministic pushdown automata to deterministic pushdown automataगैर-नियतात्मक पुशडाउन ऑटोमेटा से नियतात्मक पुशडाउन ऑटोमेटा

Explanation

Not every non-deterministic PDA can be converted into a deterministic one, because DPDAs accept only the deterministic context-free languages. NFA-to-DFA and NTM-to-DTM conversions are always possible, and every regular grammar is already context-free.हर non-deterministic PDA को deterministic में नहीं बदला जा सकता, क्योंकि DPDA केवल deterministic context-free भाषाएँ स्वीकार करते हैं। NFA से DFA और NTM से DTM में रूपांतरण हमेशा संभव है, और हर regular व्याकरण पहले से context-free है।

From Bihar STET 2025 Paper II Computer Science PYQ, 4 Nov 2025, Shift 2 (2:00 PM)

This is question 31 of Bihar STET 2025 Paper II Computer Science PYQ, 4 Nov 2025, Shift 2 (2:00 PM). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.

Asked in 2 papers