0
$\begingroup$

I've this exercise of which I'm not very sure about my solution.

Exercise:

Define the transition table about a Turing Machine that accepts words on the {a, b} alphabet where each a is followed by only two b.

My proposed solution is:

(f stands for transition function)

  • f(q0, a) = (a, q1, R)
  • f(q0, b) = HALT
  • f(q1, a) = HALT
  • f(q1, b) = (b, q2, R)
  • f(q2, a) = HALT
  • f(q2, b) = ACCEPT

I came up with this after thinking in the same way as finite state machines, even if I know are different with respect to Turing Machines (no tape, no reading/writing symbols and no right/left moves).

So, my question is, which is the best way of reasoning when I have to solve these kinds of problems?

Thank for your attention!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Welcome to cs.SE! We discourage "please check my answer" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – Raphael
    Commented Jan 11, 2018 at 11:49
  • $\begingroup$ Thank you for the suggestions! I just edit the question, I hope it's going better. Please let me know if I have to rephrase it! $\endgroup$
    – ocram
    Commented Jan 11, 2018 at 20:12
  • $\begingroup$ My personal opinion is tha the best way to solve such exercises is to convince your teacher that, even though such exercises are a wonderful source of exam questions that make your teacher's life easy, they should be kept to a minimum. Time is better spent learning a humane programming language, or designing circuits in a high-level language, and how such languages are equivalent to Turing machines (or maybe implementing a compiler to Turing machines). $\endgroup$
    – Andrej Bauer
    Commented Jul 11, 2018 at 7:57

2 Answers 2

Reset to default
0
$\begingroup$

There isn't really a "best way of reasoning". Mathematical proof is essentially a creative act and there isn't a straightforward recipe you can follow. I usually find it helps to treat Turing machine construction as a programming problem, which is basically what it is.

Improve this answer
$\endgroup$
0
0
$\begingroup$
  1. Understanding de problem: the statement says "where each a is followed by only two b", so I suppose any string of the form (abb)* is valid.
  2. This is a Regular Language, so you can make a Turing Machines that works exactly like a Finite Automaton. No need to go Left, no need to replace any symbol, no need to use extra slots.
  3. To design a TM for a more complex language, you need to define an strategy first. How are you going to mark slots and to go left and right to solve your problem? Of Course, this could be not trivial.
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.