edited by
578 views
1 votes
1 votes

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)

  1. L is decidable
  2. L′ is decidable
  3. L and L′ both are decidable
  4. L is undecidable
edited by

1 Answer

2 votes
2 votes
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 :)
edited by
Answer:

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
2 answers
4
agoh asked Dec 8, 2016
418 views
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable?Please explain.