0
$\begingroup$

What languages can be decided by a two-state TM that has two states: one accepting and one rejecting?

As a newbie in TMs, there are some definitions I am not familiar with, of which the answer is obviously dependent, like:

  • Can we draw an outgoing arrow from the Accept or Reject states?
  • Can either of these two states be the starting state?
$\endgroup$
2
  • $\begingroup$ Why not? The question is in the header. The body are minor questions that matter for a complete answer. $\endgroup$
    – Joezer
    Commented Sep 14, 2017 at 8:40
  • 1
    $\begingroup$ Ah, I see. Please ask only one question per question and use the body to elaborate the question in the header. $\endgroup$
    – adrianN
    Commented Sep 14, 2017 at 8:47

1 Answer 1

1
$\begingroup$

If there are only two states, the rejecting state and the accepting state, then the machine must start in one of those states. That means it must immediately halt, which should tell you what language it can accept.

$\endgroup$
6
  • $\begingroup$ Ok, so it looks like the languages are: 1. The empty language, 2. The language containing only the empty string. Are any of them decidable? $\endgroup$
    – Joezer
    Commented Sep 14, 2017 at 12:07
  • 2
    $\begingroup$ One of those languages is correct; the other isn't. And of course they're decidable -- you've found Turing machines that decide them! $\endgroup$ Commented Sep 14, 2017 at 12:13
  • $\begingroup$ Why arent they both correct? If the starting state is the Reject state then the language will be the empty language. And if the starting state is the Accept state then the language will be the empty string alone. What am I missing? $\endgroup$
    – Joezer
    Commented Sep 14, 2017 at 13:47
  • 2
    $\begingroup$ In the second case, you're claiming that the machine rejects every input except the empty string. How does it do that? $\endgroup$ Commented Sep 14, 2017 at 13:58
  • $\begingroup$ O... I see. So is it right that the second language would be $Sigma$*? $\endgroup$
    – Joezer
    Commented Sep 14, 2017 at 14:12

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.