1
$\begingroup$

So from what I understand, if a language is recognisable then using a TM it can be accepted and halted or rejected or halted, however a language that is decidable can be accepted and always halts on rejection?

Given the language $A_{\mathrm{DFA}} = \{\langle A \rangle\mid A \text{ is a DFA and } L(A) = \{0, 1\}^∗\}$ , I want to determine if it is decidable.

What I have come up with so far is that it is a recognisable language, I don't believe it can be rejected, only accepted and halted due to the fact once the read head comes across a blank it can just accept it. Is this the way I should be thinking? Am I correct in thinking it is not decidable or is this not a valid way to argue the point?

What should my process of thinking be when I am trying to prove it by contradiction if it is not decidable?

Thanks in advance for any tips!

Improve this question
$\endgroup$
4
  • $\begingroup$ I can just about understand your question but the way you've written it suggests to me that you're rather confused about the basic concepts. For example, you say "I have been given a DFA = {< A >|A is a DFA and L(A) = {0, 1}∗}" but that isn't a DFA: it's a language (a set of strings). A DFA is a kind of simple computer, not a set of strings. And I can't understand your attempt at proving recognizability at all. I think your first step is to review the basics, such as what a DFA and a language is, and how DFAs work. The language is decidable. $\endgroup$
    – David Richerby
    Commented Apr 13, 2017 at 11:03
  • $\begingroup$ Apologies it is a A DFA, I don't know how to format my text in the way it should be, a capital A and then DFA below that. Does that mean a language in relation to the DFA A? $\endgroup$
    – HCF3301
    Commented Apr 13, 2017 at 11:09
  • $\begingroup$ Ahh, gotcha. I'll edit it for you. Think about what it means if $L(A)\neq\{0,1\}^*$ and how you might test for that condition. $\endgroup$
    – David Richerby
    Commented Apr 13, 2017 at 11:10
  • $\begingroup$ That's exactly what you need to do, yes. $\endgroup$
    – David Richerby
    Commented Apr 13, 2017 at 12:01

1 Answer 1

Reset to default
1
$\begingroup$

Let me rephrase the question:

Is there an algorithm that, given a DFA, decides whether its language is $\{0,1\}^*$?

Such algorithms do exist, hence the corresponding set is decidable.

I'm not sure what your instructor means by "high level description of a Turing machine", but what they should have meant is "describe an algorithm that solves the problem". Hopefully you already know how to do that.

Improve this answer
$\endgroup$

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.