GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 18

Question

Let $L$ be the language containing only the single string $w,$ where
$$w = \begin{cases}
0 &\text{if India wins 2023 Cricket World Cup}\\
1 &\text{otherwise}
\end{cases}$$Which of the following statements regarding $L$ is TRUE?

• A. $L$ is regular
• B. $L$ is not recursive
• C. $L$ is not recursively enumerable
• D. $L$ is recursively enumerable but not recursive

Answer 1

$L$ is having a single string only making it finite and hence regular as well. We don't know which string $L$ has but whichever it is, $L$ is regular.

Comments

Nice question, I found this type of question in Gatebook test also

Earlier I ignored,

Now I feel. This is really a good question.

I atempted this correct.

---

Cant we think it in terms of decidability or recognizability?

---

@prajjwalsingh_11I made the same mistake by considering it as a mapping function

Answer 2

To know the exact answer, we need the TIME MACHINE. 😂😂

Just kidding, the point is after the match in 2023(we have to wait for a finite amount of time), we are 100% sure that w is “0” or “1”.

Hence decidable.

As the value of w is either “0” or “1” → Regular expression : (0+1).

Hence, it is regular too.

 

Comments

At this time when i was giving test, world cup is started and India at top position...our innocent TM need not to wait longer.😂