acacademy
[closed]

in Theory of Computation closed by
62 views
0 votes
0 votes
closed as a duplicate of: GATE CSE 2012 | Question: 24

CFG is not closed under complementation , but REC is?

in Theory of Computation closed by
by
62 views

1 comment

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

1
1

1 Answer

1 vote
1 vote
Best answer
  1. The given problem is reducible to the halting problem of turning the machine, so UNDECIDABLE.
  2. 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

selected by

2 Comments

What do you mean by being trivial?
0
0
If a property is true for every element of a set or false for every element of a set then it becomes trivial.
0
0