MadeEasy Test Series: Theory of Computation- Decidabiliy

Question

Let L be the language containing only the string S where

                         S = 0        if you will never clear the gate.

                                1       if you will clear the gate some day.

Which of the following is true? (L′ is the Complement of language L)

• A. L is decidable
• B. L′ is decidable
• C. L and L′ both are decidable
• D. L is undecidable

Answer 1

Answer will be (C)

$L$ is either $\{0\}$ or $\{1\}$. In either case $L$ is regular and hence recursive (decidable). Since $L$ is recursive so is its complement $L'$.

PS: We still don't know what strings are there in $L$. That depends on your performance in GATE :)

Comments

Can u explain more ...?? How to solve these type of problems???

---

See now..

---

Got it sir