The Halting Problem is (i) Decidable (ii) Undecidable (iii) Context-Fr — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2025 paper

Module 5: Undecidability

20252m

The Halting Problem is

(i) Decidable
(ii) Undecidable
(iii) Context-Free
(iv) Regular

Search Google Ask AI

Similar questions

FORMAL LANGUAGE & AUTOMATA THEORYWhich of the following problems is undecidable? (i) DFA acceptance (ii) NFA acceptance (iii) The Halting Problem (iv) Regular expression matching20242m Formal Language & Automata TheoryPumping Lemma for CFLs is used to prove a language is (i) Not Context-Free (ii) Regular (iii) Decidable (iv) Turing recognizable20252m Formal Language & Automata TheoryRecursively Enumerable languages are also called (i) Turing Recognizable (ii) Turing Decidable (iii) Regular (iv) Context-Free20252m FORMAL LANGUAGE & AUTOMATA THEORYProve that the halting problem for Turing machines is recursively undecidable.20227m

PreviousRecursively Enumerable languages are also called (i) Turing Recognizable (ii) Turing Decidable (iii) Regular (iv) Context-Free NextWhich of the following is used to prove many undecidability results? (i) Pumping Lemma (ii) Rice's Theorem (iii) Chomsky Normal Form (iv) Subset Construction