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

Which of the following is true for the language: { ap| p is a prime}निम्नलिखित में से कौन भाषा के लिए सत्य है: {एपी | P एक प्रमुख है}

निम्नलिखित में से कौन भाषा के लिए सत्य है: {एपी | P एक प्रमुख है}
  1. AIt is regular but not context-freeयह नियमित है लेकिन संदर्भ-मुक्त नहीं है
  2. BIt is neither regular nor context-free, but accepted by a Turing machineयह न तो नियमित है और न ही संदर्भ-मुक्त, लेकिन ट्यूरिंग मशीन द्वारा स्वीकार किया जाता है
  3. CIt is not accepted by a Turing Machineयह ट्यूरिंग मशीन द्वारा स्वीकार नहीं किया जाता है
  4. DIt is context-free but not regularयह संदर्भ-मुक्त है लेकिन नियमित नहीं है
Show answerHide answer

Correct answer: (C) It is not accepted by a Turing Machineयह ट्यूरिंग मशीन द्वारा स्वीकार नहीं किया जाता है

Explanation

Note: the answer key gives (C), but {a^p | p is prime} is accepted by a Turing machine (primality is decidable). The pumping lemmas show it is neither regular nor context-free, so (B) is correct.नोट: आधिकारिक उत्तर कुंजी (C) देती है, लेकिन {a^p | p अभाज्य है} को Turing मशीन स्वीकार करती है (अभाज्यता decidable है)। Pumping lemma दिखाते हैं कि यह न regular है और न context-free, इसलिए (B) सही है।

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

This is question 13 of Bihar STET 2025 Paper II Computer Science PYQ, 3 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