2
$\begingroup$

Calling all math buffs! ;)

A Turing machine has two states - one accepting and one non-accepting. Furthermore, the Turing machine cannot overwrite blank symbols. (Note: It's assumed that the blank symbol surrounds the input on the band and isn't itself part of any input string)

Show that the given Turing machine can only accept a regular language.

Could anyone please help me out? I can't come up with anything... (Which is unusual for me!)

Improve this question
$\endgroup$
4
  • $\begingroup$ A first idea can be thinking about that quantity of possible configurations that you can have in your restricted TM is finite. That is because the possible strings that you can have in the non-blank zone of the tape is finite. Think about building a set of states for an DFA/NFA starting from here $\endgroup$
    – ricardorr
    Nov 15, 2021 at 21:13
  • $\begingroup$ When does your machine halt? In other words, can you explain the operational semantics of your Turing machine in full? $\endgroup$
    – Yuval Filmus
    Nov 16, 2021 at 6:21
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. $\endgroup$
    – D.W. ♦
    Nov 16, 2021 at 7:15
  • $\begingroup$ ricardorr - Interesting idea, but it seems like a dead end to me. As the input string gets larger, wouldn't the number of possible configurations increase as well? Yuval Filmus - Unfortunately, the question is deliberately vague. It is a restricted TM, if that helps. D.W. - I guess it's up to you if you want to help. If I knew where to start, then I wouldn't be here, would I? ;) $\endgroup$
    – Andrew Jackson
    Nov 16, 2021 at 16:00

1 Answer 1

Reset to default
1
$\begingroup$

As it turns out, the problem is invalid - there can be Turing machines with the given specifications that can accept a non-regular language. Consider the following thought experiment:

  • Consider a word consisting of a's and b's, in which no b comes before any a. Let there be an additional character c in the beginning of the string.
  • Now imagine a Turing machine that iterates through the c, then the a's, and replaces the first b with a character that makes the machine go to the right in the accepting state, r for instance. The machine goes to the left after writing this character.
  • It now comes upon the last a, which it replaces with a character that makes it go the the left, l for instance. The machine goes to the right after writing this character.
  • The machine then goes back and forth, replacing r's with l's and l's with r's, depending on which direction it is going.
  • It will halt and accept once it reaches the initial c. (Which it will have replaced with a corresponding symbol in the very beginning of the process)

In this way, the Turing machine will accept the language of words, which contains a subword consisting of a c, followed by n a's, followed by at least n+1 b's. This is obviously not regular, because DEA's can't count. (Or more formally, use the pumping lemma to increase the number of a's to be greater than the number of b's)

Sorry for all of the confusion - this was actually a homework question! (And I assumed that it would be valid)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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