acacademy [closed]

Question

CFG is not closed under complementation , but REC is?

Comments

GATE CSE 2012 | Question: 24 (Here "Which of the following problems are decidable" is asked)

Answer 1

• A. The given problem is reducible to the halting problem of turning the machine, so UNDECIDABLE.
• B. This is an Undecidable problem. (https://cs.stackexchange.com/questions/132411/deciding-whether-complement-of-context-free-language-is-context-free)

           Not closed does not mean Undecidable.(https://gateoverflow.in/78060/undecidability) 

      C. It’s Trivial. So decidable.

      D. It’s Trivial. So decidable

Comments

What do you mean by being trivial?

---

If a property is true for every element of a set or false for every element of a set then it becomes trivial.