0
$\begingroup$

The question is:

The language L contains $DFAs$ which can accept languages equal to $\Sigma$*

prove this language is decidable.

I'm new to the Decidability topic and I don't know where should I start proving this?

reduce? Rice theorem? or we don't need things like reducing and...I would appreciate it if someone teaches me the way of thinking and proving these questions. thanks in advance.

$\endgroup$

2 Answers 2

2
$\begingroup$

Your task is to prove that the language is decidable.

Rice's theorem shows only when a language is not decidable, hence it can't be used.

About reduction: for as long as you can reduce this problem to some other decidable problem, its fine. That is, you can show that $L\le_p L'$ for some decidable $L'$ and this would ensure that $L$ is also decidable.

However, the best way to do this (in my opinion) is to directly build an algorithm that decides the question. If you want a small hint, try to answer the following: how would you decide the language of all $DFA$s that accept $\emptyset$?

$\endgroup$
2
$\begingroup$

If you have an algorithm which decides "Does DFA $M$ accept $\Sigma^*$?" you just need to check if the input is a DFA (in whatever reasonable notation you specify), if not, reject; if it is a DFA, apply the above algorithm. This decides your language.

$\endgroup$
3
  • $\begingroup$ what is the "above algorithm"? $\endgroup$
    – nir shahar
    Commented Jun 8, 2021 at 13:31
  • $\begingroup$ @nirshahar, the algorithm to see if $M$ accepts $\Sigma^*$. $\endgroup$
    – vonbrand
    Commented Jun 8, 2021 at 22:45
  • $\begingroup$ I think the OP asked how we can construct this algorithm. $\endgroup$
    – nir shahar
    Commented Jun 8, 2021 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.