Teaching Haryana (HPSC) Assistant Professor Mock Test 2025 Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Which of the following problems are decidable?
I. Checking whether two regular languages are equivalent
II. Checking whether two non-deterministic finite automata accept the same language
III. Checking whether two context free grammars generate equivalent languages
IV. Checking whether a language of a context free grammar is non-empty1
I, II and IV only
2
I and Ii only
3
I, II and III only
4
I, II, III and IV
5
Question Not Attempted