Which of the following is used to prove many undecidability results? ( — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2025 paper

Module 5: Undecidability

20252m

Which of the following is used to prove many undecidability results?

(i) Pumping Lemma
(ii) Rice's Theorem
(iii) Chomsky Normal Form
(iv) Subset Construction

Search Google Ask AI

Similar questions

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 TheoryState and prove pumping lemma for regular sets.20217m Formal Language & Automata TheoryThe Halting Problem is (i) Decidable (ii) Undecidable (iii) Context-Free (iv) Regular20252m FORMAL LANGUAGE & AUTOMATA THEORYState the pumping lemma for context-free languages.20237m

PreviousThe Halting Problem is (i) Decidable (ii) Undecidable (iii) Context-Free (iv) Regular NextDefine the terms: Alphabet, Language, Grammar, and Derivation. Explain the relationship between them with suitable examples.